[关闭]
@morehigh 2017-02-25T11:19:57.000000Z 字数 5659 阅读 1152

CQUPT 集训队专题训练（最短路）

最短路

Dijkstra算法
令G = （V，E）为一个带权有向图，把图中的顶点集合V分成两组，第一组为已求出最短路径的顶点集合S（初始时S中只有源节点，以后每求得一条最短路径，就将它对应的顶点加入到集合S中，直到全部顶点都加入到S中）；第二组是未确定最短路径的顶点集合U。在加入过程中，总保持从源节点v到S中各顶点的最短路径长度不大于从源节点v到U中任何顶点的最短路径长度。
SPFA算法
是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k< 与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。
SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的。
与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。
在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。
SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。

A - 最短路 HDU - 2544
题意：

  1. N个地点M条路，起点为1，终点为N，每条路要花费c分钟，求从起点到终点所要花费的最短时间

解题思路：

  1. 求单源最短路径，本弱用的是Dijkstra算法

代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #define inf 1e6
  7. using namespace std;
  8. int v[120],d[120],w[120][120];
  9. int n,m;
  10. void dijkstra()
  11. {
  12.     memset(v,0,sizeof(v));
  13.     for(int i=1;i<=n;i++)
  14.     d[i]=inf;
  15.     d[1]=0;
  16.     for(int i=1;i<=n;i++)
  17.     {
  18.         int x,m=inf;
  19.         for(int j=1;j<=n;j++)
  20.         {
  21.             if(!v[j]&&d[j]<m)
  22.             {
  23.                 m=d[j];
  24.                 x=j;
  25.             }
  26.         }
  27.         v[x]=1;
  28.         for(int y=1;y<=n;y++)
  29.         {
  30.             d[y]=min(d[y],d[x]+w[x][y]);
  31.         }
  32.     }
  33. }
  34. int main()
  35. {
  36.     int x,y,wi;
  37.     while(scanf("%d%d",&n,&m)!=EOF&&n+m)
  38.     {
  39.         for(int i=1;i<=n;i++)
  40.         for(int j=1;j<=n;j++)
  41.         w[i][j]=inf;
  42.         for(int i=0;i<m;i++)
  43.         {
  44.             scanf("%d%d%d",&x,&y,&wi);
  45.             w[x][y]=wi;
  46.             w[y][x]=wi;
  47.         }
  48.         dijkstra();
  49.         cout<<d[n]<<endl;
  50.     }
  51.     return 0;
  52. }

B - Wormholes POJ - 3259
题意：

  1. N (1 ≤ N ≤ 500)块田地，M (1 ≤ M ≤ 2500)条路，W (1 ≤ W ≤ 200)个虫洞，两块田地可能有多条路连接，问能不能从某条路出发，通过虫洞回到出发点的时间要比出发时间更早。

解题思路：

  1. 用spfa算法判断是否有负环存在，将最短路径入队等待松弛，如果松弛超过n次说明有负环存在，用栈和pair来存储路径和路径权值。

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<vector>
  5. #include<queue>
  6. using namespace std;
  7. #define N 505
  8. #define M 2555
  9. #define inf 0x3f3f3f3f
  10. typedef pair<int,int> pii;
  11. #define mp(x,y) make_pair(x,y)
  13. vector<pii>E[N];
  14. bool vis[N];
  15. int cnt[N];
  16. int dis[N];
  17. int n,m1,m2;
  18. void ini()
  19. {
  21.     memset(cnt,0,sizeof(cnt));
  22.     memset(vis,0,sizeof(vis));
  23.     for(int i=1;i<=n;i++)
  24.     E[i].clear();
  25. }
  26. bool SPFA(int n)
  27. {
  28.     queue<int> que;
  29.     while(!que.empty()) que.pop();
  30.     for(int i=1;i<=n;i++) {
  31.         que.push(i);
  32.         vis[i]=true;
  33.         dis[i]=inf;
  34.     }
  35.     while(!que.empty())
  36.     {
  37.         int u=que.front();
  38.         que.pop();
  39.         vis[u]=false;
  40.         for(int i=0;i<E[u].size();i++) 
  41.         { 
  42.            int v=E[u][i].first,cost=E[u][i].second;
  43.            if(dis[v]>dis[u]+cost)
  44.             {
  45.                 dis[v]=dis[u]+cost;
  46.                 if(!vis[v])
  47.                 {
  48.                     vis[v]=true;
  49.                     que.push(v);
  50.                     if(++cnt[v]>n) return false;
  51.                 }
  52.             }
  53.         }
  54.     }
  55.     return true;
  56. }
  57. int main()
  58. {
  59.     int T;
  60.     scanf("%d",&T);
  61.     while(T--)
  62.     {
  63.         ini();
  64.         scanf("%d%d%d",&n,&m1,&m2);
  65.         while(m1--)
  66.         {
  67.             int u,v,w;
  68.             scanf("%d%d%d",&u,&v,&w);
  69.             E[u].push_back(mp(v,w));
  70.             E[v].push_back(mp(u,w));
  71.         }
  72.         while(m2--)
  73.         {
  74.             int u,v,w;
  75.             scanf("%d%d%d",&u,&v,&w);
  76.             E[u].push_back(mp(v,-1*w));
  77.         }
  78.         if(SPFA(n)) printf("NO\n");
  79.         else printf("YES\n");
  80.     }
  81.     return 0;
  82. }

C - Stockbroker Grapevine POJ - 1125
题意：

  1. 两个人传递信息需要时间，有n个人传递一条消息，以其中一个人为起点传递此消息，问是否能传递给所有人，并且时间最短。

解题思路：

  1. 用floyd算法求出以任意一个人为起点，任意一个人为终点的最短时间。然后枚举出每一个人为起点时并把消息传个每个人的时间，求出最短时间。
  2. Floyd的原理是动态规划，设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<vector>
  5. #include<queue>
  6. #define inf 0x3f3f3f
  8. using namespace std;
  9. int n;
  10. int map[200][200];
  12. void floyd()
  13. {
  14.     for(int k=1;k<=n;k++)
  15.     {
  16.         for(int i=1;i<=n;i++)
  17.         {
  18.             for(int j=1;j<=n;j++)
  19.             map[i][j]=min(map[i][k]+map[k][j],map[i][j]);
  20.         }
  21.     }
  22.     int ans=inf,x;
  23.     for(int i=1;i<=n;i++)
  24.     {
  25.         int pa=0;
  26.         for(int j=1;j<=n;j++)
  27.         {
  28.             if(pa<map[i][j])
  29.             pa=map[i][j];
  30.         }
  31.         if(ans>pa)
  32.         {
  33.             ans=pa;
  34.             x=i;
  35.         }
  36.     }
  37.     if(ans!=inf)
  38.     cout<<x<<" "<<ans<<endl;
  39.     else
  40.     cout<<"disjoint"<<endl;
  41. }
  42. int main()
  43. {
  44.     int t,x,w;
  45.     while(~scanf("%d",&n)&&n)
  46.     {
  47.         for(int i=1;i<=n;i++)
  48.         for(int j=1;j<=n;j++)
  49.         {
  50.             if(i==j)
  51.             map[i][j]=0;
  52.             else
  53.             map[i][j]=inf;
  54.         }
  55.         for(int i=1;i<=n;i++)
  56.         {
  57.             scanf("%d",&t);
  58.             while(t--)
  59.             {
  60.                 scanf("%d%d",&x,&w);
  61.                 map[i][x]=w;
  62.             }
  63.         }
  64.         floyd();
  65.     }
  66.     return 0;
  67. }

E - 最短路径问题 HDU - 3790
题意：

  1. 给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

解题思路：

  1. 有两个边权值的最短路径问题，用dijstra算法维护路径最短和花费至最小。由于输入的边可能重复，花费大小可能不一样，所以要先维护出此路径的最小花费。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #define inf 1000000
  9. using namespace std;
  10. typedef pair<int,int> p;
  11. struct Node
  12. {
  13.     int dis,cost;
  14. }edge[1024][1024];
  15. int d[1024],v[1024];
  16. int value[1024];
  17. int n,m;
  18. //vector<int> edge[1024];
  19. void dijkstra(int s)
  20. {
  21.     memset(v,0,sizeof(v));
  22.     fill(d+1,d+n+1,inf);
  23.     d[s]=0;
  24.     value[s]=0;
  25.     for(int i=1;i<=n;i++)
  26.     {
  27.         int x,m=inf;
  28.         for(int j=1;j<=n;j++)
  29.         {
  30.             if(!v[j]&&d[j]<m)
  31.             {
  32.                 m=d[j];
  33.                 x=j;
  34.             }
  35.         }
  36.         v[x]=1;
  37.         for(int j=1;j<=n;j++)
  38.         {
  39.             if(d[j]>d[x]+edge[x][j].dis )
  40.             {
  41.                 d[j]=d[x]+edge[x][j].dis ;
  42.                 value[j]=value[x]+edge[x][j].cost ;
  43.             }
  44.             if(d[j]==d[x]+edge[x][j].dis)
  45.             {
  46.                 if(value[j]>value[x]+edge[x][j].cost)
  47.                 value[j]=value[x]+edge[x][j].cost;
  48.             }
  49.         }
  50.     }
  51. }
  52. int main()
  53. {
  54.     int a,b,c,cc;
  55.     while(scanf("%d%d",&n,&m)!=EOF&&n+m)
  56.     {
  57.         for(int i=1;i<=n;i++)
  58.         for(int j=1;j<=n;j++)
  59.         {
  60.             edge[i][j].dis=inf;
  61.             edge[i][j].cost=inf;
  62.         }
  63.         for(int i=0;i<m;i++)
  64.         {
  65.             scanf("%d%d%d%d",&a,&b,&c,&cc);
  66.             if(edge[a][b].dis>c)
  67.             {
  68.                 edge[a][b].dis=edge[b][a].dis=c;
  69.                 edge[a][b].cost=edge[b][a].cost=cc;
  70.             }
  71.             if(edge[a][b].dis==c)
  72.             {
  73.                 if(edge[a][b].cost>cc)
  74.                 edge[a][b].cost=edge[b][a].cost=cc;
  75.             }
  77.         }
  78.         int x,y;
  79.         scanf("%d%d",&x,&y);
  80.         dijkstra(x);
  81.         cout<<d[y]<<" "<<value[y]<<endl;
  82.     }
  83.     return 0;
  84. }

F - Choose the best route HDU - 2680
题意：

  1. n, m , s,(n<1000,m<20000,1=<s<=n)，n代表汽车站的数量，m代表两个相连的车站的数量，s代表Kiki所要到达的终点，w个车站是Kiki的起点，求出Kiki从w中的一个车站上车，所花费的时间最少

解题思路：

  1. 由于dijkstra算法求得是单源到各个点的最短路径，所以我们将Kiki所要到达的终点当作起点，求出单源到多个终点的最短距离

代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #define inf 0x3f3f3f
  9. using namespace std;
  10. int w[1024][1024];
  11. int d[1024],v[1024];
  12. int n,m,s;
  13. void dijkstra()
  14. {
  15.     memset(v,0,sizeof(v));
  16.     for(int i=1;i<=n;i++)d[i]=inf;
  17.     d[s]=0;
  18.     for(int i=1;i<=n;i++)
  19.     {
  20.         int x,m=inf;
  21.         for(int j=1;j<=n;j++)
  22.         {
  23.             if(!v[j]&&d[j]<m)
  24.             {
  25.                 x=j;
  26.                 m=d[j];
  27.             }
  28.         }
  29.         v[x]=1;
  30.         for(int j=1;j<=n;j++)
  31.         d[j]=min(d[j],d[x]+w[x][j]);
  32.     }
  33. }
  34. int main()
  35. {
  36.     int p,q,t,x,e;
  37.     while(scanf("%d%d%d",&n,&m,&s)!=EOF)
  38.     {
  39.         for(int i=1;i<=n;i++)
  40.          for(int j=1;j<=n;j++)
  41.         w[i][j]=inf;
  42.         for(int i=0;i<m;i++)
  43.         {
  44.             scanf("%d%d%d",&p,&q,&t);
  45.             if(w[q][p]>t)
  46.             w[q][p]=t;
  47.         }
  48.         dijkstra();
  49.         scanf("%d",&x);
  50.         int ans=inf;
  51.         for(int i=0;i<x;i++)
  52.         {
  53.             scanf("%d",&e);
  54.             ans=min(ans,d[e]);
  55.         }
  56.         if(ans==inf)
  57.         cout<<"-1"<<endl;
  58.         else
  59.         cout<<ans<<endl;
  60.     }
  61.     return 0;
  62. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注