60分4个WA求条

#include <iostream>
#include <cstring>
#include <bitset>
#include <queue>

using namespace std;

inline char getch()
{
    static char buf[100005], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100005, stdin), p1 == p2) ? EOF : *p1 ++ ;
}
template<typename Type>
inline void read(Type &x)
{
    char c; bool t;
    x = t = 0, c = getch();
    while (c < '0' || c > '9') t |= (c == '-'), c = getch();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getch();
    x = t ? -x : x;
}

const int N = 2e3 + 5, M = 5e3 + 5;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;

int to[M], we[M], ne[M];
int head[N], pre[M], idx;
int n, m, dist[N];
int q[N], tt, res[N];
int in[N], out[N]; // s~i  i~...
bitset<M> tag;

void add(int u, int v, int w)
{
    pre[ ++ idx] = u;
    to[idx] = v;
    we[idx] = w;
    ne[idx] = head[u];
    head[u] = idx;
}

priority_queue<pii, vector<pii>, greater<pii>> p;
bitset<N> st;
void Dijkstra(int s)
{
    memset(dist, 0x3f, sizeof dist);
    st.reset();
    tt = 0;

    while (!p.empty()) p.pop();
    dist[s] = 0;
    p.push(pii{0, s});

    while (!p.empty())
    {
        int ver = p.top().second;
        p.pop();

        if (st[ver]) continue;
        st[ver] = true;

        q[ ++ tt] = ver;

        for (int i = head[ver]; i; i = ne[i])
        {
            int v = to[i], w = we[i];
            if (dist[v] > dist[ver] + w)
            {
                dist[v] = dist[ver] + w;
                p.push(pii{dist[v], v});
            }
        }
    }
}

void Toposort(int s)
{
    for (int i = 1; i <= n; i = -~ i) out[i] = in[i] = 0;
    tag.reset();
    for (int i = 1; i <= m; i = -~ i)
    {
        if (dist[pre[i]] + we[i] == dist[to[i]])
        {
            tag[i] = true;
        }
    }
    for (int i = tt; i >= 1; -- i)
    {
        for (int j = head[q[i]]; j; j = ne[j])
        {
            if (tag[j]) out[q[i]] += out[to[j]];
        }
        out[q[i]] ++ ; // form me to myself
    }
    in[s] = 1; // from me to myself
    for (int i = 1; i <= tt; i = -~ i)
    {
        for (int j = head[q[i]]; j; j = ne[j])
        {
            if (tag[j]) in[to[j]] += in[q[i]];
        }
    }
    for (int i = 1; i <= m; i = -~ i)
    {
        if (tag[i]) res[i] += 1ll * max(1, in[pre[i]]) * max(1, out[to[i]]) % mod, res[i] %= mod;
    }
}

int main()
{
    read(n), read(m);
    for (int i = 1; i <= m; i = -~ i)
    {
        int u, v, w;
        read(u), read(v), read(w);
        add(u, v, w);
    }
    for (int i = 1; i <= n; i = -~ i)
    {
        Dijkstra(i);
        Toposort(i);
    }
    for (int i = 1; i <= m; i = -~ i) printf("%d\n", res[i]);
    return 0;
}