如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。
输入格式:
第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi,分别表示第i条有向边的出发点、目标点和长度。
输出格式:
一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)
输入样例#1:
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出样例#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<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 using namespace std;
7 const int MAXN=500001;
8 struct node
9 {
10 int u;
11 int v;
12 int w;
13 int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 void add(int x,int y,int z)
18 {
19 edge[num].u=x;
20 edge[num].v=y;
21 edge[num].w=z;
22 edge[num].next=head[x];
23 head[x]=num++;
24 }
25 int dis[MAXN];
26 int vis[MAXN];
27 int n,m,s;
28 void SPFA(int s)
29 {
30 dis[s]=0;
31 vis[s]=1;
32 queue<int>q;
33 q.push(s);
34 while(q.size()!=0)
35 {
36 int p=q.front();
37 q.pop();
38 vis[p]=0;
39 for(int i=head[p];i!=-1;i=edge[i].next)
40 {
41 int to=edge[i].v;
42 if(dis[to]>dis[p]+edge[i].w)
43 {
44 dis[to]=dis[p]+edge[i].w;
45 if(vis[to]==0)
46 {
47 q.push(to);
48 vis[to]=1;
49 }
50 }
51 }
52 }
53 for(int i=1;i<=n;i++)
54 {
55 printf("%d ",dis[i]);
56 }
57 }
58 int main()
59 {
60
61 scanf("%d%d%d",&n,&m,&s);
62 for(int i=1;i<=n;i++)head[i]=-1,dis[i]=2147483647;
63 for(int i=1;i<=m;i++)
64 {
65 int x,y,z;
66 scanf("%d%d%d",&x,&y,&z);
67 add(x,y,z);
68 }
69 SPFA(s);
70 return 0;
71 }