洛谷【模板】单源最短路径

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#1：

输出样例#1：

0 2 4 3

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15

对于40%的数据：N<=100，M<=10000

对于70%的数据：N<=1000，M<=100000

对于100%的数据：N<=10000，M<=500000

样例说明：

 1 #include <cstdio>
 2 #include <limits.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxne = 600001;
 7 const int maxnn = 20001;
 8 const unsigned long long int inf = 6000000000;
 9 int n,e,s,t,cnt;
10 int last[maxne],q[maxne],check[maxnn];
11 long long dis[maxnn];
12 bool is[maxnn],fuhuan;
13 int read()
14 {
15     int x=0,f=1; char ch=getchar();
16     while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
17     while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;
18 }
19 struct line {int to,next,v;}l[maxne];
20 void add(int u,int v,int w) { l[++cnt].to=v; l[cnt].next=last[u]; last[u]=cnt; l[cnt].v=w; }
21 void spfa(int a)
22 {
23     for(int i=1;i<=n;i++) dis[i]=inf;
24     dis[a]=0; is[a]=1; q[0]=a; check[a]++;
25     int head=0,tail=1;
26     while(head!=tail)
27     {
28         int now=q[head++];
29         if(head==n+1) head=0;
30         for(int i=last[now];i;i=l[i].next)
31         {
32             if( dis[now]+l[i].v<dis[l[i].to] && dis[now]!=inf)
33             {
34                 dis[l[i].to]=dis[now]+l[i].v;
35                 if(!is[l[i].to])
36                 {
37                     is[l[i].to]=1;
38                     if(dis[l[i].to]<dis[q[head]])
39                     {
40                         head--; if(head==-1) head=n;
41                         q[head]=l[i].to;
42                         check[l[i].to]++;
43                         if(check[l[i].to]==n) { fuhuan=1; return;}
44                     }
45                     else
46                     {
47                         q[tail++]=l[i].to;
48                         if(check[l[i].to]==n) { fuhuan=1; return;}
49                         if(tail==n+1) tail=0;
50                     }
51                 }
52             }
53         }
54         is[now]=0;
55     } 
56 }
57 int main()
58 {
59     int u,v,w;
60     n=read();e=read(); 
61     s=read();
62     for(int i=1;i<=e;i++)
63     {
64         u=read();v=read(); w=read();
65         add(u,v,w);
66     }
67     spfa(s);
68     for(int i=1;i<=n;i++)
69     {
70         if(dis[i]==inf) cout<<"2147483647 ";
71         else cout<<dis[i]<<" "; 
72     }
73     return 0;
74 }