Bellman-Ford 0pts 悬关

Zinuo_zheng @ 2024-07-06 18:02:46

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int u, v, w;
} e[100005];
int n, m, s;
int f[100005];
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= m; i++)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    memset(f, 0x3f, sizeof f);
    f[s] = 0;
    for(int i = 1; i < n; i++)
        for(int j = 1; j <= m; j++)
            f[e[j].v] = min(f[e[j].v], f[e[j].u] + e[j].w);
    for(int i = 1; i <= n; i++)
        printf("%d ", f[i]);
    return 0;
}

by Kazeno_Akina @ 2024-07-06 18:19:26

@Zinuo_zheng m\le 2\times 10^5，边的数组开小了。

by Zinuo_zheng @ 2024-07-06 18:20:48

现在全T了

by Zinuo_zheng @ 2024-07-06 18:21:11

@Kazeno_Akina

by Kazeno_Akina @ 2024-07-06 18:24:43

@Zinuo_zheng 您的复杂度是 O(nm) 的，而此题中 n\times m 会到达 2\times 10^{10} 的可怕量级，因此会 T。

别惦记你那 Bellman-Ford 了，学学 Dijkstra 或者 SPFA 吧。

by Zinuo_zheng @ 2024-07-06 18:30:21

好的，已关

by Lyw_Cyq_01 @ 2024-07-06 18:48:18

@Kazeno_Akina Bellman-Ford 跟 SPFA 没啥区别吧？你应该指的是堆优化 SPFA 吧。

by Kazeno_Akina @ 2024-07-06 18:53:26

@Lyw_Cyq_01 SPFA 在随机数据下表现优于 Bellman-Ford。

by Kazeno_Akina @ 2024-07-06 18:53:59

@Lyw_Cyq_01 当然如果毒瘤出题人造数据，二者的最劣复杂度是一致的。

by Lyw_Cyq_01 @ 2024-07-06 18:54:33

@Kazeno_Akina 确实是，但是资深出题人会告诉你什么叫做 SPFA 似了（当然 Bellman-Ford 也一样）。

by Kazeno_Akina @ 2024-07-06 18:58:03

@Lyw_Cyq_01 不如说 SPFA 似的可能性比 Bellman-Ford 小一点

但是负权图你也确实只能写这俩啊。