求HACK数据？

RT

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4 + 5;
const int MOD = 1000000007;
struct node {
    int id,val;
    bool operator < (const node &x) const {
        return x.val < val;
    }
};
struct edge {
    int from,to,val,id;
};
int n,m; 
vector <edge> V[N];
edge Eg[N];
int d[N],vis[N];
ll res[N],res1[N],res2[N],OK[N];
void dfs1(int u) {
    for(int i = 0;i < V[u].size();i ++) {
        int v = V[u][i].to;
        if(d[v] == d[u] + V[u][i].val) {
            OK[V[u][i].id] = 1;
            res1[v] = (res1[v] + res1[u]) % MOD;
            dfs1(v);
        }
    }
}
void dfs2(int u) {
    if(V[u].size() == 0) {
        res2[u] = 1;
        return ;
    }
    res2[u] = 1;
    for(int i = 0;i < V[u].size();i ++) {
        int v = V[u][i].to;
        if(d[v] == d[u] + V[u][i].val) {
            dfs2(v);
            res2[u] = (res2[u] + res2[v]) % MOD;
        }
    }
}
void dij() {
    for(int i = 1;i <= n;i ++) {
        memset(d,0x3f,sizeof d);
        memset(res1,0,sizeof res1);
        memset(res2,0,sizeof res2);
        memset(vis,0,sizeof vis);
        memset(OK,0,sizeof OK);
        priority_queue <node> q;
        q.push((node){i,0});
        d[i] = 0;
        while(! q.empty()) {
            node u = q.top();
            q.pop();
            if(vis[u.id]) continue;
            vis[u.id] = 1;
            for(int i = 0;i < V[u.id].size();i ++) {
                int v = V[u.id][i].to;
                if(d[u.id] + V[u.id][i].val < d[v]) {
                    d[v] = d[u.id] + V[u.id][i].val;
                    q.push((node){v,d[v]});
                }
            }
        }
        res1[i] = 1;
        dfs1(i);
        dfs2(i);
        for(int j = 1;j <= n;j ++) {
            if(OK[j]) {
                res[j] = (res[j] + res1[Eg[j].from] * res2[Eg[j].to] % MOD) % MOD; 
            } 
        }
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i ++) {
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        V[u].push_back((edge){u,v,w,i});
        Eg[i] = (edge){u,v,0,0};
    }
    dij(); 
    for(int i = 1;i <= n;i ++) {
        printf("%lld\n",res[i] % MOD);
    }
    return 0;
}