题意：
给定无重边无自环的带正权无向连通图，问最多删除几条边能保持所有点对的最短距离不变
\(n\le 300\)
思路：
删除边 \(u\overset{w}{-}v\) 当且仅当原图中存在其它路径的长度小于等于 \(w\)，即存在中间点 \(k\)，使得 \(d(u,k)+d(k,v)\le w\)
因为每次都在原图中找其他路径，所以（相比在删除若干边后的新图上找）找到的可能性是最大的。这样会不会删太多了？答案是不会，只需证明这样得到的子图符合题意：
考虑原图中 \(u\) 到 \(v\) 的最短路径中边数最多的那条，记为 \(path\)。若 \(path\) 仅有一条边则 \(u\) 到 \(v\) 的距离没变，符合题意；若 \(path\) 不止一条边则把 \(path\) 拆成两部分，由归纳法可以证明符合题意
可以用 floyd 实现
const int N = 310;
int n, m, ans;
bool g[N][N]; //还有没有此边
ll d[N][N];
void sol() {
memset(d, 0x3f, sizeof d);
cin >> n >> m;
while(m--) {
int x, y, z; cin >> x >> y >> z;
d[x][y] = d[y][x] = z;
g[x][y] = true;
}
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(d[i][j] >= d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j],
ans += g[i][j], g[i][j] = 0;
cout << ans;
}