#贪心，#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;
}

发现性质：如果 a->b 需要 $w$ 的距离，如果存在一条 a->p->b 的路径使距离也为 $w$ ，那 a->b 的这条边就可以不需要了。

$n\le300$ ，可以枚举 a b p 三个点，代码如下。

    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            bool flag=0;
            for(int p=1;p<=n;p++){
                if(p==i||p==j) continue;
                if(dis[i][j]==dis[i][p]+dis[j][p]){
                    flag=1;
                    break;
                } 
            }
            if(!flag) ans++;
        }
    }