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

首先讲解一下链式前向星是什么。简单的来说就是用一个数组（用结构体来表示多个量）来存一张图，每一条边的出结点的编号都指向这条边同一出结点的另一个编号（怎么这么的绕）

如下面的程序就是存链式前向星。（不用链式前向星用邻接矩阵过不了，因为数据大会超空间限制）

 struct node{

     int quan,to,qian;

 }lian[];

 int qian[];//开始都为0，是个边界

 void add(int x,int y,int z){

     lian[++ans].qian=qian[x];//存前一个的编号，自己可以模拟一下很好理解的

     lian[ans].quan=z;//存对应的比边权

     lian[ans].to=y;//与之相连的点是哪一个存下来

     qian[x]=ans;//变成当前编号方便存下一个

 }

学会了链式前向星，接下来就是Dijkstra算法。

Dijkstra算法是基于贪心的算法，它是寻找每一点相连的边的最小值，在对整个图进行更新，做n-1次，也可以认为是一种动态规划，但不适用于有负边的情况，以后我会对它进行堆优化，现在用的Dijkstra是未经优化的版本。

在很多高级算法的书上都会提到，我就不画图和证明正确性了，借助程序讲

 1 #include<bits/stdc++.h>
 2 using namespace std;

 struct node{

     int quan,to,qian;

 }lian[];

 int n,m,s,dis[],ans,qian[];

 bool vis[];

 void add(int x,int y,int z){

     lian[++ans].qian=qian[x];

     lian[ans].quan=z;

     lian[ans].to=y;

     qian[x]=ans;

 }//链式前向星存储

 void dijkstra(){

     memset(vis,false,sizeof(vis));

     memset(dis,0x3f,sizeof(dis));

     dis[s]=;

     int now=s;

     vis[s]=true     for (int i=;i<n;i++){//要将整张图寻找,所以要找n-1次

             vis[now]=true;//记录是否已经遍历过

             int p=qian[now];

             while (p!=){//边界是0前面已经说明，要自己理解

                 if (not vis[lian[p].to]&&(lian[p].quan+dis[now]<dis[lian[p].to]))

                     dis[lian[p].to]=lian[p].quan+dis[now];

                 p=lian[p].qian;

             } //链式前向星寻找，每次更新没有遍历过的点的最小值

             int minn=0x7fffffff;

             for (int j=;j<=n;j++)

               if (not vis[j]&&dis[j]<minn){

                   minn=dis[j];

                   now=j;//找最小的没遍历的点继续更新

             }

     }

 }

 int main(){

     scanf("%d%d%d",&n,&m,&s);

     for (int i=;i<=m;i++){

         int a,b,c;

         scanf("%d%d%d",&a,&b,&c);

         add(a,b,c);//处理读入数据

     }

     dijkstra();

     for (int i=;i<=n;i++){

       if (dis[i]>) printf("%d ",);

       else printf("%d ",dis[i]);//输出结果

     }

 }