【模板】单源最短路径spfa

P3371 【模板】单源最短路径

发现自己的博客居然没有spfa？？这样是不完整的!!(雾

贴板子qwq

 1 #include<queue>
 2 #include<cstdio>
 3 #include<iostream>
 4 using namespace std;
 5 const int maxn = 10010, maxm = 500050, inf = 2147483647;
 6 int n, m, s, num = 0;
 7 int head[maxm], dis[maxn];
 8 bool vis[maxn];
 9 struct edge {
10     int nxt, to, dis;
11 }e[maxm];
12 void add(int from, int to, int dis) {
13     e[++num].nxt = head[from];
14     e[num].to = to;
15     e[num].dis = dis;
16     head[from] = num;
17 }
18 void spfa() {
19     queue<int>q;
20     for(int i = 1; i <= n; i++) {
21         dis[i] = inf;
22         vis[i] = 0;
23     }
24     q.push(s);
25     dis[s] = 0;
26     vis[s] = 1;
27     while(!q.empty()) {
28         int u = q.front();
29         q.pop();
30         vis[u] = 0;//日常忘记打这一句QAQ
31         for(int i = head[u]; i; i = e[i].nxt) {
32             int v = e[i].to;
33             if(dis[v] >= dis[u]+e[i].dis) {
34                 dis[v] = dis[u]+e[i].dis;
35                 if(!vis[v]) {
36                     vis[v] = 1;
37                     q.push(v);
38                 }
39             }
40         }
41     }
42 }
43 int main() {
44     scanf("%d%d%d", &n, &m, &s);
45     for(int i = 1; i <= m; i++) {
46         int f, g, k;
47         scanf("%d%d%d", &f, &g, &k);
48         add(f, g, k);
49     }
50     spfa();
51     for(int i = 1; i <= n; i++) 
52         printf("%d ", dis[i]);
53     return 0;
54 }

觉得自己码风超棒哈哈哈哈哈哈哈

但博客中代码字体丑的一比QAQ还不会改QAQ

10/17 今天日常敲板子， wa的我一脸懵逼，发现我建了双向边orz

总之岁月漫长，然而值得期待。