- #include<iostream>
- #include<queue>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef pair<int, int> pii;
- const int maxn=1e5+5, maxm=2e5+5;
- struct edge
- {
- int t, w; edge * nxt;
- edge(int to, int len, edge * next){ t=to, w=len, nxt=next; }
- };
- edge * head[maxn];
- void add(int u, int v, int len){ head[u]=new edge(v, len, head[u]); }
- int dis[maxn], v[maxn], n, m, s;
- void dijkstra(int s)
- {
- memset(dis, 0x3f, sizeof dis); //sizeof 不是一个函数, 而是运算符, 这种用法是可以的
- priority_queue<pii, vector<pii>, greater<pii>> Q; // 小根堆
- dis[s]=0;
- Q.push(make_pair(0, s));
- while(!Q.empty())
- {
- int x=Q.top().second;
- if(v[x]) { Q.pop(); continue;} //continue; 之前一定要 pop 掉, 否则会死循环
- else { v[x]=true; dis[x]=Q.top().first; Q.pop();}
- for(edge *p=head[x]; p; p=p->nxt) if (!v[p->t]) Q.push(make_pair(dis[x]+p->w, p->t));
- }
- }
- int main()
- {
- scanf("%d%d%d", &n, &m, &s);
- for(int i=1, x, y, z; i<=m; i++) scanf("%d%d%d", &x, &y, &z), add(x, y, z);
- dijkstra(s);
- for(int i=1; i<=n; i++) printf("%d", dis[i]);
- printf("\n");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2977562.html