题目：给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
解法：spfa算法。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<queue>
6 using namespace std;
7 typedef long long LL;
8
9 const int N=10010,M=500010;
10 const LL INF=2147483647;
11 int n,m,st,len=0;
12 int vis[N],last[N];
13 LL dis[N];
14 struct edge{int x,y,next;LL d;}a[2*M];
15 queue<int> q;
16
17 void ins(int x,int y,LL d)
18 {
19 a[++len].x=x,a[len].y=y,a[len].d=d;
20 a[len].next=last[x],last[x]=len;
21 }
22 void spfa()
23 {
24 for (int i=1;i<=n;i++) dis[i]=INF;
25 memset(vis,0,sizeof(vis));
26 while (!q.empty()) q.pop();
27 dis[st]=0, vis[st]=1;
28 q.push(st);
29 while (!q.empty())
30 {
31 int x=q.front();
32 q.pop(); vis[x]=0;
33 for (int i=last[x];i;i=a[i].next)
34 {
35 int y=a[i].y;
36 if (dis[x]+a[i].d<dis[y])
37 {
38 dis[y]=dis[x]+a[i].d;
39 if (!vis[y]) vis[y]=1, q.push(y);
40 }
41 }
42 }
43 }
44 int main()
45 {
46 scanf("%d%d%d",&n,&m,&st);
47 int x,y; LL d;
48 memset(last,-1,sizeof(last));
49 for (int i=1;i<=m;i++)
50 {
51 scanf("%d%d%lld",&x,&y,&d);
52 ins(x,y,d);
53 }
54 spfa();
55 for (int i=1;i<=n;i++)
56 printf("%lld ",dis[i]);
57 printf("\n");
58 return 0;
59 }