洛谷P3371单源最短路径Dijkstra版（链式前向星处理）

 1 struct node{
 2     int quan,to,qian;
 3 }lian[500010];
 4 int qian[10010];//开始都为0，是个边界
 5 void add(int x,int y,int z){
 6     lian[++ans].qian=qian[x];//存前一个的编号，自己可以模拟一下很好理解的
 7     lian[ans].quan=z;//存对应的比边权
 8     lian[ans].to=y;//与之相连的点是哪一个存下来
 9     qian[x]=ans;//变成当前编号方便存下一个
10 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node{
 4     int quan,to,qian;
 5 }lian[500010];
 6 int n,m,s,dis[10010],ans,qian[10010];
 7 bool vis[10010]; 
 8 void add(int x,int y,int z){
 9     lian[++ans].qian=qian[x];
10     lian[ans].quan=z;
11     lian[ans].to=y;
12     qian[x]=ans;
13 }//链式前向星存储
14 void dijkstra(){
15     memset(vis,false,sizeof(vis));
16     memset(dis,0x3f,sizeof(dis));
17     dis[s]=0;
18     int now=s;
19     vis[s]=true20     for (int i=1;i<n;i++){//要将整张图寻找,所以要找n-1次
21             vis[now]=true;//记录是否已经遍历过
22             int p=qian[now];
23             while (p!=0){//边界是0前面已经说明，要自己理解
24                 if (not vis[lian[p].to]&&(lian[p].quan+dis[now]<dis[lian[p].to]))
25                     dis[lian[p].to]=lian[p].quan+dis[now];
26                 p=lian[p].qian;
27             } //链式前向星寻找，每次更新没有遍历过的点的最小值
28             int minn=0x7fffffff;
29             for (int j=1;j<=n;j++)
30               if (not vis[j]&&dis[j]<minn){
31                   minn=dis[j];
32                   now=j;//找最小的没遍历的点继续更新
33             }
34     }
35 }
36 int main(){
37     scanf("%d%d%d",&n,&m,&s);
38     for (int i=1;i<=m;i++){
39         int a,b,c;
40         scanf("%d%d%d",&a,&b,&c);
41         add(a,b,c);//处理读入数据
42     }
43     dijkstra();
44     for (int i=1;i<=n;i++){
45       if (dis[i]>100000000) printf("%d ",2147483647);
46       else printf("%d ",dis[i]);//输出结果
47     } 
48 }