题目传送门
解题思路:
传送门 https://www.cnblogs.com/lipeiyi520/p/10340361.html
AC 代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- struct kkk {
- int from,to,v,next;
- }e[500001];
- int n,m,s,head[500001],q,w,p,tot,ans[500001];
- bool vis[500001];
- void add(int q,int w,int p) {
- e[++tot].from = q;
- e[tot].to = w;
- e[tot].v = p;
- e[tot].next = head[q];
- head[q] = tot;
- }
- void dijkstra(int s) {
- memset(vis,0,sizeof(vis));
- ans[s] = 0;
- for(int i = 1;i <= n; i++) {
- int id = 0,sum = 0x3f3f;
- for(int j = 1;j <= n; j++)
- if(!vis[j] && sum>= ans[j])
- sum = ans[j],id = j;
- vis[id] = 1;
- for(int j = head[id];j;j = e[j].next)
- ans[e[j].to] = min(ans[e[j].to],ans[id] + e[j].v);
- }
- }
- int main() {
- scanf("%d%d%d",&n,&m,&s);
- for(int i = 1;i <= n; i++)
- ans[i] = 0x3f3f3f3f;
- for(int i = 1;i <= m; i++) {
- scanf("%d%d%d",&q,&w,&p);
- add(q,w,p);
- }
- dijkstra(s);
- for(int i = 1;i <= n; i++) {
- if(ans[i] == 0x3f3f3f3f) printf("2147483647");
- else
- printf("%d",ans[i]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3136327.html