磊神的铁路

首先用 floyd 预处理出各点之间的最短距离，之后对每条边判断。

令 $a,b,c$ 分别为边连接的两个点和边的长度，$dis$ 为两点之间最短距离。显然，当 $c \gt dis$ 时可以直接删去。当 $c = dis$ 时，我们就看 $a,b$ 两点之间是否还有其他边数大于一且长度等于 $dis$ 路径能相互到达，如果有就删除，否则保留。

因为如果存在这样一条路径，就说明该路径上有多条边，且这些边长度小于 $dis$，这些边能使该路径上的某些点到其他点的距离更短，而直接连接 $a,b$ 两点的该边就可以删去了，判断方法可以在 floyd 更新边时，给被更新的两个点打个标记，之后O(1)判断即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
ll g[330][330];
bool has[330][330];
struct edge_info{
    int a, b;
    ll c;
}edg[N];
void floyd(int n){
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(g[i][j] >= g[i][k] + g[k][j]){
                    if(k != i && k != j && i != j)
                        has[i][j] = has[j][i] = 1;
                    g[i][j] = g[j][i] = g[i][k] + g[k][j];
                } 
}
int main(){
    int n, m, idx = 0;
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i <= n; i++)
        g[i][i] = 0;
    for(int i = 0; i < m; i++){
        int a, b;
        ll c;
        scanf("%d%d%lld", &a, &b, &c);
        edg[idx++] = {a, b, c};
        g[b][a] = min(g[b][a], c);
        g[a][b] = g[b][a];
    }
    floyd(n);
    int cnt = 0;
    for(int i = 0; i < idx; i++){
        int a = edg[i].a, b = edg[i].b;
        ll c = edg[i].c;
        if(g[a][b] < c) cnt++;
        else if(g[a][b] == c && has[a][b]) cnt++;
    }
    printf("%d", cnt);
}