关于 SPFA，它活了

P4779 【模板】单源最短路径（标准版）

chenbs @ 2024-08-11 08:11:14

SPFA AC

算法来源：

来源：CSDN

https://blog.csdn.net/JacaJava/article/details/82528037

by fjy666 @ 2024-08-11 08:12:03

能不能发一下代码

by chenbs @ 2024-08-11 08:12:50

@fjy666 代码来自于 CSDN，你可以看 这里

by XuYueming @ 2024-08-11 08:24:18

@chenbs 你试试？

by wxin @ 2024-08-11 08:28:34

帅！

by zhangjiahe__ @ 2024-08-11 08:39:36

@fstqwq 请求加强数据

by ChangeYuAN @ 2024-08-11 08:54:58

伸颈

by KK_lang @ 2024-08-11 08:59:13

@chenbs 你还是麻烦了

AC

#include<bits/stdc++.h>
using namespace std;

const int NR = 1e5 + 10;

int n, m, s;

int dis[NR];

struct Edge
{
    int to, w;
};
vector<Edge> g[NR]; 
bool flag[NR];

struct cmp
{
    bool operator()(const int a, const int b)
    {
        return dis[a] > dis[b];
    }
};

void spfa(int s)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(flag, false, sizeof(flag));
    dis[s] = 0;
    priority_queue<int, vector<int>, cmp> q;
    q.push(s);
    flag[s] = true;
    while (!q.empty())
    {
        int x = q.top();
        q.pop();
        flag[x] = false;
        for (auto y:g[x])
        {
            if (dis[x] + y.w >= dis[y.to]) continue;
            dis[y.to] = dis[x] + y.w;
            if (flag[y.to]) continue;
            flag[y.to] = true;
            q.push(y.to);
        }
    }
}

int main()
{
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back((Edge){v, w});
    }
    spfa(s);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    return 0;
}

by chenbs @ 2024-08-11 09:16:17

@XuYueming 你这个题的确数据很强，卡得我只有 44 分了

by WZLsuanzai @ 2024-10-05 17:17:10

重生之sperm归来

|