最短路

//orz...高中的时候苦练最短路，然而那年noip没有考。再次写起来倍感亲切啊。

//先整理一波最短路的知识。

一、存图方式

1.邻接矩阵

顾名思义，就是以矩阵的方式来存图啦。有n个点，那么图就是map[n][n]啦。

2.邻接表

和邻接矩阵不同。邻接表是用两点之间的关系来存图的。比如有一条路是x-->y，那么就是在下标为x的数组里插入y，表示存在一条路是x-->y。第一次cpp的邻接表学到了一波新操作。

1 //代码来源：hdoj2722
2 //建立邻接表
3 struct point{
4     int v,num;
5     point(int a,int b){num=a;v=b;}
6 };
7 vector<point> S[maxn*maxn];

ps.第一次用cpp的vector有点点激动。真鸡儿好用啊orz

3.边集数组+链式前向星

（留坑，有点忘了）

二、最短路算法

1.单源最短路—dijkstra

求一个图中两个点之间最短距离的最快的一种方法，要求路径的花费不能有负的。
时间复杂度：O(ElogE)

（大佬们的代码姿势学不来，继续我P式代码风格）

 1 //dijk+邻接矩阵
 2 void dijk(int st){
 3     memset(V,0,sizeof(V));
 4     V[st]=1;
 5     for (int i=1;i<=n;i++) F[i]=A[st][i];
 6     F[st]=Inf;
 7     for (int i=1;i<=n;i++){
 8         int k=st;
 9         for (int j=1;j<=n;j++){
10             if (!V[j] && F[j]<F[k]) k=j;
11         }
12         V[k]=1;
13         for (int j=1;j<=n;j++){
14             if (F[j]>F[k]+A[k][j] && !V[j]) F[j]=F[k]+A[k][j]; 
15         }
16     }
17 }

2.单源最短路—spfa

代码量较小，速度又不错，经常与其他算法组合出现，可以用来判断负环。（突然想起来没练判负环的题）

 1 //spfa+邻接矩阵
 2 void spfa(int st){
 3     queue<int> Q;
 4     memset(V,0,sizeof(V));
 5     V[st]=1;F[st]=0;T[st]=0;
 6     Q.push(st);
 7     while (!Q.empty()){
 8         int pos=Q.front();
 9         Q.pop();
10         V[pos]=0;
11         for (int i=1;i<=n;i++){
12             int temp=F[pos]+A[pos][i];
13             if (temp<F[i]){
14                 F[i]=temp;
15                 T[i]=T[pos]+B[pos][i];
16                 if (!V[i]){
17                     Q.push(i);
18                     V[i]=1;
19                 }
20             }
21             else if(temp==F[i] && T[i]>T[pos]+B[pos][i]){
22                 T[i]=T[pos]+B[pos][i];
23                 if (!V[i]){
24                     Q.push(i);
25                     V[i]=1;
26                 }
27             }
28         }
29     }
30 }

 1 //spfa+邻接表
 2 void spfa(){
 3     queue<int> Q;
 4     for (int i=1;i<=(n+1)*(m+1);i++) F[i]=Inf;
 5     memset(V,0,sizeof(V));
 6     F[1]=0;
 7     V[1]=1;
 8     Q.push(1);
 9     while (!Q.empty()){
10         int pos=Q.front();
11         Q.pop();
12         V[pos]=0;
13         for (int i=0;i<S[pos].size();i++){
14             int temp=F[pos]+S[pos][i].v;
15             int yy=S[pos][i].num;
16             if (temp<F[yy]){
17                 F[yy]=temp;
18                 if (!V[yy]){
19                     Q.push(yy);
20                     V[yy]=1;
21                 }
22             }
23         }
24     }
25 }

（留坑，spfa+链式前向星）

3.多元最短路—floyd

经常做预处理用，能处理出来图中任意两个点之间的最短距离，时间复杂度O(n^3) 。

 1 //floyd+邻接矩阵
 2 void floyd(){
 3     for (int k=1;k<=n;k++){
 4         for (int i=1;i<k;i++){
 5             for (int j=k+1;j<=n;j++){
 6                 if (A[i][j]<A[i][k]+A[k][j]){
 7                     A[i][j]=A[i][k]+A[k][j];
 8                     path[i][j]=path[i][k];
 9                 }
10             }
11         }
12     }
13 }

4.bell-man

 1 bool bellman_ford(int s){
 2     queue<int> Q;
 3     memset(inq,0,sizeof(0));
 4     memset(cnt,0,sizeof(cnt));
 5     for (int i=0;i<n;i++) d[i]=inf;
 6     d[s]=0;
 7     inq[s]=1;
 8     Q.push(s);
 9     while (!Q.empty()){
10         int u=Q.front();
11         Q.pop();
12         inq[u]=0;
13         for (int i=0;i<G[u].size();i++){
14             Edge &e=edges[G[u][i]];
15             if (d[u]<inf && d[e.to]>d[u]+e.dist){
16                 d[e.to]=d[u]+e.dist;
17                 p[e.to]=G[u][i];
18                 if (!inq[e.to]){
19                     Q.push(e.to);
20                     inq[e.to]=1;
21                     if (++cnt[e.to]>n) return 0;
22                 }
23             }
24         }
25     }
26 }