过样例0分求调

#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1500 + 10;
const int maxm = 5000 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9;
int n, m, top, d[maxn], f[maxn], g[maxn], stk[maxn], deg[maxn], res[maxm];
bool vis[maxn], used[maxm];
vector<int> E;
vector<tuple<int, int, int> > G, e[maxn];
priority_queue<pii, vector<pii>, greater<pii> > pq;
void ckadd(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        e[u].emplace_back(v, w, i);
        G.emplace_back(u, v, w);
    }
    for (int st = 1; st <= n; st++) {
        for (int i = 1; i <= n; i++) f[i] = g[i] = deg[i] = used[i] = vis[i] = 0, d[i] = inf;
        for (pq.emplace(0, st), d[st] = 0; pq.size(); ) {
            auto [W, u] = pq.top(); pq.pop();
            if (vis[u]) continue; vis[u] = true;
            for (auto [v, w, id] : e[u])
                if (d[v] > d[u] + w)
                    d[v] = d[u] + w, pq.emplace(d[v], v);
        } int id = 0; for (auto [u, v, w] : G)
            if (++id && d[u] + w == d[v]) used[id] = true;
        for (int i = 1; i <= m; i++) if (used[i]) ++deg[get<1>(G[i - 1])];
        for (stk[++top] = st, f[st] = 1, E.clear(); top; ) {
            int u = stk[top--]; E.push_back(u);
            for (auto [v, w, id] : e[u]) if (used[id]) {
                ckadd(f[v], f[u]);
                if (--deg[v] == 0) stk[++top] = v;
            }
        }
        reverse(E.begin(), E.end());
        for (int u : E) {
            ++g[u]; for (auto [v, w, id] : e[u]) if (used[id])
                ckadd(g[u], g[v]);
        } id = 0; for (auto [u, v, w] : G) if (used[++id])
            res[id] = (res[id] + (ll)f[u] * g[v]) % mod;
    }
    for (int i = 1; i <= m; i++) cout << res[i] << '\n';
    return 0;
}

给个hack也行