#贪心，#floyed

由数据范围，我们知道，这是一个类 floyed 的 $n^3$ 状物。

将每一条最短路放到邻接矩阵上。

发现较长的路径长度可能是由较短的路径拼接而成。
一条路径如果是可以被拼接形成的，那么显然没有必要建一条边，将它打一个标记。 这个过程类似于 floyed。

最终统计有多少路径没有被打标记，其数量即为答案。

需要注意无向边与有向边的区别，只统计一半的有向边就是无向边数量。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e2 + 10;
int n, e[N][N], vis[N][N];
int main(){
	cin >> n;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++) cin >> e[i][j];
	
	for(int k = 1; k <= n; k ++){
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= n; j ++){
				if(i==k||j==k) continue;//路径不能被自己拼接而成
				if(e[i][j] == e[i][k] + e[k][j]) vis[i][j] = 1;//打标记
			}
		}
	}
	int cnt = 0;
	for(int i = 1; i <= n; i ++){
		for(int j = i+1; j <= n; j ++){//只统计一般有向边，即为无向边数量
			cnt+=(!vis[i][j]);
		}
	}
	cout << cnt;
	return 0;
}