求助

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=1505;
ll dis[MAXN][MAXN];
bool rq[MAXN][5101];
ll start[MAXN];
ll vis[MAXN],m,n;
const ll MOD=1e9+7;
struct ed{
    ll l,r,d,x;
}ge[5001];
bool operator<(ed a,ed b)
{
    return a.l<b.l;
}
struct poll{
    ll s,d;
};
bool operator<(poll a,poll b)
{
    return a.d<b.d;
}
void djk(ll s)
{
    memset(vis,0,sizeof(vis));
    priority_queue<poll>q;
    q.push({s,0});
    dis[s][s]=0;
    while (!q.empty())
    {
        poll p=q.top();
        q.pop();
        if (vis[p.s]) continue;
        vis[p.s]=1;
//      cout<<s<<' '<<p.e<<endl;
        for (ll i=start[p.s];ge[i].l==p.s;i++)
            if (ge[i].d+dis[s][p.s]<dis[s][ge[i].r]){
                dis[s][ge[i].r]=ge[i].d+dis[s][p.s];
                q.push({ge[i].r,dis[s][ge[i].r]});
            }
    }
}
ll s0[MAXN]={0};
ll cc[MAXN][MAXN]={0};
ll cz[MAXN][MAXN]={0};
void tg(ll s,ll n)
{
    for (ll i=start[n];ge[i].l==n;i++)
        if (rq[s][i])
        {
            cc[s][ge[i].r]+=cc[s][n];
            s0[ge[i].r]--;
            if (s0[ge[i].r]==0)
            tg(s,ge[i].r);
        }
}
void rg(ll s,ll n)
{
    vis[n]=1;
    cz[s][n]=1;
    for (ll i=start[n];ge[i].l==n;i++)
        if (rq[s][i])
        {
            if (!vis[ge[i].r])
                rg(s,ge[i].r);
            cz[s][n]+=cz[s][ge[i].r];
        }
}
void make(ll s)
{
    memset(s0,0,sizeof(s0));
    for (ll i=1;i<=m;i++)
        if (rq[s][i])
            s0[ge[i].r]++;
    cc[s][s]=1;
    tg(s,s);
    memset(vis,0,sizeof(vis));
    rg(s,s);
}
ll ans[5001]={0};
int main()
{
    cin>>n>>m;
    for (ll i=1;i<=m;i++){
        cin>>ge[i].l>>ge[i].r>>ge[i].d;
        ge[i].x=i;
    }
    sort(ge+1,ge+m+1);
    for (ll i=1;i<=m;i++)
        if (ge[i].l!=ge[i-1].l)
            start[ge[i].l]=i;
    memset(dis,0x3f,sizeof(dis));
    ll inf=dis[0][0];
    for (ll i=1;i<=n;i++)
        djk(i);
    for (int i=1;i<=n;i++)
        for (int ii=1;ii<=m;ii++)
            rq[i][ii]=(dis[i][ge[ii].l]+ge[ii].d==dis[i][ge[ii].r]);
    for (ll i=1;i<=n;i++)
        make(i);
/*  
    cout<<endl;
    for (ll i=1;i<=n;i++){
        for (ll ii=1;ii<=n;ii++)
            cout<<cz[i][ii]<<' ';
        cout<<endl;
    }*/
    for (ll i=1;i<=n;i++)
        for (ll ii=1;ii<=m;ii++)
            if (rq[i][ii]){
                ans[ge[ii].x]+=cc[i][ge[ii].l]*cz[i][ge[ii].r];
                ans[ge[ii].x]%=MOD;
            }
    for (ll i=1;i<=m;i++)
        cout<<ans[i]<<endl;
}