____TAT____ @ 2023-12-06 18:27:43
#include <iostream>
#include <limits.h>
#include <queue>
using namespace std;
int n, m, s, head[1000005], to[4000005], nxt[4000005], gsize, dis[1000005], ans[1000005];
int len[1000005];
bool f[1000005];
int cnt;
inline int read()
{ // 快读
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
s = s * 10 + ch - 48, ch = getchar();
return s * w;
}
inline void write(int x)
{ // 快写
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
void addedge(int u, int v, int l)
{
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
len[cnt] = l;
}
void SPFA(){
queue<int> q;
dis[s] = 0;
q.push(s);
while(!q.empty()){
int u = q.front();
for(int i = head[u]; i; i = nxt[i]){
int v = to[i];
if(dis[u] + len[i] < dis[v]){
dis[v] = dis[u] + len[i];
if(!f[i]){
q.push(v);
f[i] = true;
}
}
}
q.pop();
f[u] = false;
}
}
int main()
{
n = read();
m = read();
s = read();
for (int i = 1; i <= n; i++)
{
dis[i] = INT_MAX;
head[i] = -1;
}
for (int i = 1; i <= m; i++)
{
int x, y, l;
x = read();
y = read();
l = read();
addedge(x, y, l);
addedge(y, x, l);
}
SPFA();
ans[1] = 1;
for (int i = 1; i <= n; i++)
{
write(dis[i]);
cout << " ";
}
return 0;
}4 WA + 1 TLE
by CEFqwq @ 2023-12-06 19:16:23
spfa 死了。
by __zhuruirong__ @ 2023-12-10 15:50:08
@TAT 这题用SPFA骗分还不如用Bellman-Ford骗分好（虽然正解还是dijkstra）
Bellman-Ford
SPFA
dijkstra
by __zhuruirong__ @ 2023-12-10 15:51:02
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node {
int nxt, num;
bool operator < (const Node& x) const {
return num > x.num;
}
};
vector<Node> E[N];
int ans[N], n, m, s;
bool vis[N];
void dijkstra(int s) {
memset(vis, 0, sizeof vis);
memset(ans, 0x3f, sizeof ans);
ans[s] = 0;
priority_queue<Node> q;
q.push({s, 0});
while(!q.empty()) {
int now = q.top().nxt; q.pop();
if(vis[now])
continue;
vis[now] = true;
for(int i = 0; i < E[now].size(); i++)
if(ans[E[now][i].nxt] > ans[now] + E[now][i].num) {
ans[E[now][i].nxt] = ans[now] + E[now][i].num;
if(!vis[E[now][i].nxt])
q.push({E[now][i].nxt, ans[E[now][i].nxt]});
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> s;
while(m--) {
int x, y, w;
cin >> x >> y >> w;
E[x].push_back({y, w});
}
dijkstra(s);
for(int i = 1; i <= n; i++)
cout << ans[i] << " ";
}