SPFA 70分求调
查看原帖
SPFA 70分求调
785917
Chthollian楼主2023/10/3 21:06

目前的问题:队列模拟出错(换成queue后AC)

#include <bits/stdc++.h>
using namespace std;
int n, m, s, x, y, u, v, node[10005], vis[10005], q[10005], head = 1, last = 1;
long long w, dis[10005];
struct Edge
{
    int to, next;
    long long v;
} es[500005];
int main()
{
    // freopen("P3371_2.in", "r", stdin);
    // freopen("P3371_2.out", "w", stdout);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> w;
        es[i].to = y;
        es[i].next = node[x];
        node[x] = i;
        es[i].v = w;
    }
    for (int i = 1; i <= n; i++)
    {
        dis[i] = 0x3f3f3f3f3f3f3f3f;
    }
    dis[s] = 0, vis[s] = 1;
    q[head] = s;
    while (head <= last)
    {
        u = q[head];
        head++;
        vis[u] = 0;
        for (int i = node[u]; i; i = es[i].next)
        {
            v = es[i].to;
            if (dis[u] + es[i].v >= dis[v])
            {
                continue;
            }
            dis[v] = dis[u] + es[i].v;
            if (vis[v] == 0)
            {
                vis[v] = 1;
                q[++last] = v;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == 0x3f3f3f3f3f3f3f3f)
        {
            cout << 2147483647 << " ";
        }
        else
        {
            cout << dis[i] << " ";
        }
    }
    return 0;
}
2023/10/3 21:06
加载中...