求助

跑 n 遍dij的做法，全Wa

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
typedef long long LL;
const int N=1505,M=5005,MOD=1e9+7;

int fst[N],nxt[M<<1],T[M<<1],W[M<<1],tot;
void add_edge(int a,int b,int c){nxt[++tot]=fst[a];fst[a]=tot;T[tot]=b;W[tot]=c;}

int n,m;
int dis[N], ans[M<<1];
bool inque[N];
int fa[N],lst[N],val[N]; 
int deg[N];

void dij(int p){
    priority_queue<PII,vector<PII>,greater<PII> > Q;
    memset(dis,0x3f,sizeof(dis));
    memset(inque,0,sizeof(inque));
    memset(fa,0,sizeof(fa));
    memset(lst,0,sizeof(lst));
    memset(val,0x3f,sizeof(val));
    memset(deg,0,sizeof(deg));

    dis[p]=0;
    Q.push({0,p});
    while(Q.size()){
        auto t=Q.top(); Q.pop();
        int x=t.second;
        if(inque[x]) continue;
        inque[x]=1;
        for(int i=fst[x];i;i=nxt[i]){
            int j=T[i];
            if(dis[j]==dis[x]+W[i]){
                if(W[i]<val[j]){
                    deg[fa[j]]--;
                    fa[j]=x; lst[j]=i; val[j]=W[i];
                    deg[x]++;
                }
            }
            else if(dis[j]>dis[x]+W[i]){
                fa[j]=x; lst[j]=i; val[j]=W[i];
                deg[x]++;
                dis[j]=dis[x]+W[i];
                if(!inque[j]) Q.push({dis[j],j});
            }
        }
    }
}

void bfs(){
//  cout<<"\n";
//  for(int i=1;i<=n;i++) cout<<i<<" "<<fa[i]<<" "<<deg[i]<<"\n";
//  cout<<"\n";
    queue<PII> Q;
    for(int i=1;i<=n;i++)
        if(!deg[i])
            Q.push({i,1});
    while(Q.size()){
        auto t=Q.front(); Q.pop();
        int nw=t.first, dep=t.second;
        ans[lst[nw]]=(ans[lst[nw]]+dep)%MOD; 
        deg[fa[nw]]--;
        if(!deg[fa[nw]]){
            dep++;
            Q.push({fa[nw],dep});
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
        add_edge(v,u,w);
    }

    for(int i=1;i<=n;i++){
        dij(i);
        bfs();
    }

    for(int i=1;i<=tot;i+=2)
        printf("%d\n",(ans[i]+ans[i+1])%MOD);
    return 0;
}