60分求调

开O2WA，关O2RE，求调:

#include<bits/stdc++.h>
using namespace std;
const int N=1.5e3+5,M=5e3+5,mod=1e9+7;
struct graph{
    int head[N],Next[M],ver[M],tot=0;
    long long val[M],cnt[N];
    void merge(int x,int y,long long z){
        ver[++tot]=y,val[tot]=z,Next[tot]=head[x],head[x]=tot,cnt[y]++;
    }
}g1;
int n,m,p[N],tot=0,cnt[N];
long long dist[N],cnt1[N],cnt2[N],ans[M];
bool inq[N],ing[N];
queue<int>q;
void spfa(int s){
    memset(dist,0x3f,sizeof dist);
    memset(inq,0,sizeof inq);
    q.push(s),dist[s]=0,inq[s]=1;
    while(!q.empty()){
        int x=q.front();
        inq[x]=0,q.pop();
        for(int i=g1.head[x];i;i=g1.Next[i]){
            int y=g1.ver[i];
            long long z=g1.val[i];
            if(dist[x]+z<dist[y]){
                dist[y]=dist[x]+z;
                if(!inq[y])q.push(y),inq[y]=1;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y;
        long long z;
        cin>>x>>y>>z;
        g1.merge(x,y,z);
    }
    for(int i=1;i<=n;++i){
        tot=0;
        memset(ing,0,sizeof ing);
        memset(cnt,0,sizeof cnt);
        spfa(i);
        for(int j=1;j<=n;++j)
            for(int k=g1.head[j];k;k=g1.Next[k]){
                int d=g1.ver[k];
                long long v=g1.val[k];
                if(dist[j]+v==dist[d])ing[k]=1,cnt[d]++;
            }
        memset(inq,0,sizeof inq);
        memset(cnt1,0,sizeof cnt1);
        memset(cnt2,0,sizeof cnt2);
        cnt1[i]=1,q.push(i),inq[i]=1;
        while(!q.empty()){
            int x=q.front();
            q.pop(),p[++tot]=x;
            for(int j=g1.head[x];j;j=g1.Next[j]){
                if(!ing[j])continue;
                int y=g1.ver[j];
                if(!inq[y]){
                    cnt1[y]=(cnt1[y]+cnt1[x])%mod;  
                    if(!--cnt[y])q.push(y),inq[y]=1;
                }
            }
        }
//      cout<<"p:";
//      for(int i=1;i<=tot;++i)cout<<p[i]<<' ';
//      cout<<endl;
        for(int j=tot;j;--j){
            int x=p[j];
            cnt2[x]=1;
//          cout<<x<<endl;
            for(int k=g1.head[x];k;k=g1.Next[k]){
                if(!ing[k])continue;
                int y=g1.ver[k];
                cnt2[x]=(cnt2[x]+cnt2[y])%mod;
//              cout<<y<<' ';
            }
//          cout<<endl;
        }
        for(int j=1;j<=n;++j)
            for(int k=g1.head[j];k;k=g1.Next[k]){
                if(!ing[k])continue;
                int d=g1.ver[k];
                ans[k]=(ans[k]+cnt1[j]*cnt2[d]%mod)%mod;
//              cout<<k<<' '<<j<<' '<<d<<endl;
            }
//      cout<<"ans:";
//      for(int j=1;j<=m;++j)cout<<ans[j]<<' ';
//      cout<<endl;
//      cout<<"cnt1:";
//      for(int j=1;j<=n;++j)cout<<cnt1[j]<<' ';
//      cout<<endl;
//      cout<<"cnt2:";
//      for(int j=1;j<=n;++j)cout<<cnt2[j]<<' ';
//      cout<<endl;
    }
    for(int i=1;i<=m;++i)cout<<ans[i]<<endl;
    return 0;
}