哪里被卡了

tai_chi @ 2023-10-28 12:26:23

by tai_chi @ 2023-10-28 12:26:49

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define IOS                     \
    ios::sync_with_stdio(NULL); \
    cin.tie(NULL);              \
    cout.tie(NULL)
#define pii pair<int, int>
const int maxn = 15005, maxm = 50005, mod1 = 1e9 + 7, inf = 0x3f3f3f3f;
int n, m;
int head[maxn], tot;
struct node
{
    int v, w, nxt;
} e[maxm];
void add(int u, int v, int w)
{
    e[++tot].v = v;
    e[tot].w = w;
    e[tot].nxt = head[u];
    head[u] = tot;
}
int dis[maxn];
bool vis[maxn];
bool ins[maxn]; // 在最短路图中
int in[maxn];   // 入度
void dij(int st)
{
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[st] = 0;
    priority_queue<pii> q; // dis v
    q.push({0, st});
    while (!q.empty())
    {
        pii now = q.top();
        q.pop();
        int u = now.second;
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v, w = e[i].w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!vis[v])
                {
                    q.push({dis[v], v});
                }
            }
        }
    }
    memset(ins, 0, sizeof(ins));
    for (int u = 1; u <= n; u++)
    {
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v, w = e[i].w;
            if (dis[v] == dis[u] + w)
            {
                ins[i] = 1;
                in[v]++;
            }
        }
    }
}
int tp[maxn], t;
void topsort()
{
    memset(tp, 0, sizeof(tp));
    t = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (!in[i])
        {
            tp[++t] = i;
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
        {
            if (!ins[i])
                continue;
            int v = e[i].v;
            in[v]--;
            if (!in[v])
            {
                tp[++t] = v;
                q.push(v);
            }
        }
    }
}
int cnt1[maxn], cnt2[maxn];
int ans[maxm];
void solve(int st)
{
    memset(cnt1, 0, sizeof(cnt1));
    memset(cnt2, 0, sizeof(cnt2));
    cnt1[st] = 1;
    for (int i = 1; i <= n; i++)
    {
        int u = tp[i];
        for (int j = head[u]; j; j = e[j].nxt)
        {
            if (!ins[j])
                continue;
            int v = e[j].v;
            cnt1[v] += cnt1[u], cnt1[v] %= mod1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cnt2[i] = 1;
    }
    for (int i = n; i >= 1; i--)
    {
        int u = tp[i];
        for (int j = head[u]; j; j = e[j].nxt)
        {
            if (!ins[j])
                continue;
            int v = e[j].v;
            cnt2[u] += cnt2[v], cnt2[u] %= mod1;
        }
    }
    for (int i = n; i >= 1; i--)
    {
        int u = tp[i];
        for (int j = head[u]; j; j = e[j].nxt)
        {
            if (!ins[j])
                continue;
            int v = e[j].v;
            ans[j] += cnt1[u] * cnt2[v] % mod1, ans[j] %= mod1;
        }
    }
}
signed main()
{
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    for (int i = 1; i <= n; i++)
    {
        dij(i);
        topsort();
        solve(i);
    }
    for (int i = 1; i <= m; i++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}

by tai_chi @ 2023-10-28 14:02:31

破案了，这题卡 dij，换成 spfa 过了。

by tai_chi @ 2023-10-28 15:54:01

案破错了，我自己 dij 写假了。。。

小丑竟是我自己

by JunYao0 @ 2023-10-30 17:47:54

6