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;
}
记录
样例能过,求助dalao
by Lyw_Cyq_01 @ 2024-07-06 19:00:21
@Kazeno_Akina 确实是的,所以究竟有什么好争的?那两个算法除了负权图也都没啥用。
by Kazeno_Akina @ 2024-07-06 19:08:25
@Lyw_Cyq_01 意思是,在负权图问题中,很可能存在题目卡 Bellman-Ford 而 SPFA 能够通过。所以 SPFA 还有点用。
by Lyw_Cyq_01 @ 2024-07-06 19:09:56
@Kazeno_Akina 嗯。毕竟 bellman-ford 的时间复杂度固定。
by SwethessPotion @ 2024-07-08 20:33:48
@Kazeno_Akina @Lyw_Cyq_01 所以这题不是没有负权边吗?所以还是好好写堆优化 Dijkstra 把
by Kazeno_Akina @ 2024-07-08 20:39:57
@SwethessPotion 只是在讨论 SPFA 尚存的使用价值。