POJ 最短路问题题号汇总
参考：《算法图解》第7章 《算法导论》第24章
Dijkstra算法又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。
它的主要特点是以起始点为中心向外层扩展(广度优先搜索思想)，直到扩展到终点为止。迪杰斯特拉算法采用贪心策略。
使用二维数组 e 来存储顶点之间边的关系，初始值如下。
我们还需要用一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程，如下。
我们将此时 dis 数组中的值称为最短路的“估计值”。
既然是求 1 号顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。当选择了 2 号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”，即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。为什么呢？你想啊，目前离 1 号顶点最近的是 2 号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 1 号顶点到 2 号顶点的路程进一步缩短了。
既然选了 2 号顶点，接下来再来看 2 号顶点有哪些出边呢。有 2->3 和 2->4 这两条边。先讨论通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。也就是说现在来比较 dis[3]和 dis[2]+e[2][3]的大小。其中 dis[3]表示 1 号顶点到 3 号顶点的路程。dis[2]+e[2][3]中 dis[2]表示 1 号顶点到 2 号顶点的路程，e[2][3]表示 2->3 这条边。所以 dis[2]+e[2][3]就表示从 1 号顶点先到 2 号顶点，再通过 2->3 这条边，到达 3 号顶点的路程。
我们发现 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新为 10。这个过程有个专业术语叫做“松弛”。即 1 号顶点到 3 号顶点的路程即 dis[3]，通过 2->3 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛 1 号顶点到其余各个顶点的路程。
同理通过 2->4（e[2][4]），可以将 dis[4]的值从 ∞ 松弛为 4（dis[4]初始为 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新为 4）。
刚才我们对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为：
接下来，继续在剩下的 3、4、5 和 6 号顶点中，选出离 1 号顶点最近的顶点。通过上面更新过 dis 数组，当前离 1 号顶点最近是 4 号顶点。此时，dis[4]的值已经从“估计值”变为了“确定值”。下面继续对 4 号顶点的所有出边（4->3，4->5 和 4->6）用刚才的方法进行松弛。松弛完毕之后 dis 数组为：
继续在剩下的 3、5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 3 号顶点。此时，dis[3]的值已经从“估计值”变为了“确定值”。对 3 号顶点的所有出边（3->5）进行松弛。松弛完毕之后 dis 数组为：
继续在剩下的 5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 5 号顶点。此时，dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边（5->4）进行松弛。松弛完毕之后 dis 数组为：
最后对 6 号顶点所有点出边进行松弛。因为这个例子中 6 号顶点没有出边，因此不用处理。到此，dis 数组中所有的值都已经从“估计值”变为了“确定值”。
最终 dis 数组如下，这便是 1 号顶点到其余各个顶点的最短路径。
OK，现在来总结一下刚才的算法。算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。基本步骤如下：
将所有的顶点分为两部分：已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。最开始，已知最短路径的顶点集合 P 中只有源点一个顶点。我们这里用一个 book[ i ]数组来记录哪些点在集合 P 中。例如对于某个顶点 i，如果 book[ i ]为 1 则表示这个顶点在集合 P 中，如果 book[ i ]为 0 则表示这个顶点在集合 Q 中。设置源点 s 到自己的最短路径为 0 即 dis=0。若存在源点有能直接到达的顶点 i，则把 dis[ i ]设为 e[s][ i ]。同时把所有其它（源点不能直接到达的）顶点的最短路径为设为 ∞。在集合 Q 的所有顶点中选择一个离源点 s 最近的顶点 u（即 dis[u]最小）加入到集合 P。并考察所有以点 u 为起点的边，对每一条边进行松弛操作。例如存在一条从 u 到 v 的边，那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径，这条路径的长度是 dis[u]+e[u][v]。如果这个值比目前已知的 dis[v]的值要小，我们可以用新值来替代当前 dis[v]中的值。重复第 3 步，如果集合 Q 为空，算法结束。最终 dis 数组中的值就是源点到所有顶点的最短路径。
Floyd算法：解决任意两点间的最短路径的一种算法，即多源最短路径，可以正确处理有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。
https://www.cnblogs.com/wangyuliang/p/9216365.html
#include int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 //读入n和m，n表示顶点个数，m表示边的条数 scanf("%d %d",&n,&m); //初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; //读入边 for(i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&t3); e[t1][t2]=t3; } //Floyd-Warshall算法核心语句 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j] ) e[i][j]=e[i][k]+e[k][j]; //输出最终的结果 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("d",e[i][j]); } printf("\n"); } return 0; }
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线
Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
#include <iostream> #include <cstring> using namespace std; #define maxn 105 #define INF 1e9 int a[maxn][maxn]; bool vis[maxn]; //vis记录某个点是否已经包含在已找到最短路的集合中 int dis[maxn]; //dis记录某个点到vis集合的最短路 int n; void Dij(int x,int y) { //初始化dis、vis数组 for(int i=1;i<=n;i++) { dis[i]=a[1][i]; vis[i]=false; } //起点（路口1）加入vis数组，包含在已找到的最短路的集合中 vis[x]=true; int p; for(int i=1;i<=n;i++) { int minn=INF; for(int j=1;j<=n;j++) { if(vis[j]==false && dis[j]<minn) { minn=dis[j]; p=j; } } //路口p加入vis数组 vis[p]=true; for(int j=1;j<=n;j++) { if(!vis[j]&&dis[p]+a[p][j]<dis[j]) { dis[j]=dis[p]+a[p][j]; } } } } int main() { int m; while(cin>>n>>m) { if(n==0&&m==0) break; int x,y,z; //邻接矩阵初始化为无穷大 memset(a,INF,sizeof(a)); //输入m条路并存入邻接矩阵，无向图的邻接矩阵是对称的 while(m--) { cin>>x>>y>>z; a[x][y]=a[y][x]=z; } //迪杰斯特拉算法 Dij(1,n); cout<<dis[n]<<endl; } return 0; }这个题比第一题只是多了一个花费，在路线长度一样时再比较花费，我用上面的模板做竟然超时了，参考了一下https://www.cnblogs.com/wenzhixin/p/7405802.html。cin换成scanf，cout换成printf之后竟然AC了！！！
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
Input
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t)
Output
输出 一行有两个数， 最短距离及其花费。
//#include<iostream> #include<stdio.h> #include<string.h> using namespace std; #define inf 1e9 int map[1001][1001],prize[1001][1001]; //存储两点的长度 //存储两点的花费 void dij(int s,int t,int n) //x：起点。y：终点 { int i,j,p; bool vis[1001]; //记录某个点是否包含在最短路径中 int disd[1001]; //记录某个点到vis集合的最短距离 int disp[1001]; //记录某个点到vis集合的最少花费 for( i=1;i<=n;i++) { disd[i]=map[s][i]; disp[i]=prize[s][i]; } for (i=1;i<=n;i++) { vis[i]=false; } vis[s]=true; for( i=1;i<n;i++) { int minn=inf; for( j=1;j<=n;j++) { if(vis[j]==false && disd[j]<minn) { minn=disd[j]; p=j; } } vis[p]=true; for( j=1;j<=n;j++) { if(vis[j]==false && map[p][j]<inf) { if(disd[p]+map[p][j]<disd[j]) { disd[j]=disd[p]+map[p][j]; disp[j]=disp[p]+prize[p][j]; } else if(disd[p]+map[p][j]==disd[j] && disp[j]>disp[p]+prize[p][j]) disp[j]=disp[p]+prize[p][j]; } } } printf("%d %d\n",disd[t],disp[t]); //cout<<disd[t]<<" "<<disp[t]<<endl; } int main() { int n,m,s,t,a,b,d,p,i,j; while(scanf("%d%d",&n,&m), n+m != 0) { for( i=1;i<=n;i++) { for( j=1;j<=n;j++) { map[i][j]=prize[i][j]=inf; } } for( i=1;i<=m;i++) { scanf("%d%d%d%d",&a,&b,&d,&p); if(map[a][b]>d) { map[a][b]=map[b][a]=d; prize[a][b]=prize[b][a]=p; } else if(map[a][b]==d && prize[a][b]>p) { map[a][b]=map[b][a]=d; prize[a][b]=prize[b][a]=p; } } scanf("%d%d",&s,&t); dij(s,t,n); } return 0; }网上都说这个题的输入比较难，但是我卡在了题意上，完全没搞懂这些坐标的单位，看了题解才明白，输入里面的坐标的单位都是里，人和地铁的速度单位里面的是公里。
代码网上一大堆，但是没看懂输入部分是怎么处理的，为什么直接if(a == -1 && b == -1)j=0就可以了？？？
#include <iostream> #include <cstring> #include <deque> #include <cmath> #include <queue> #include <stack> #include <list> #include <map> #include <set> #include <string> #include <vector> #include <cstdio> #include <bitset> #include <algorithm> using namespace std; #define Debug(x) cout << #x << " " << x <<endl #define Memset(x, a) memset(x, a, sizeof(x)) const int INF = 0x3f3f3f3f; typedef long long LL; typedef pair<int, int> P; #define FOR(i, a, b) for(int i = a;i < b; i++) #define MAX_N 2520 int n; double G[MAX_N][MAX_N]; struct Point{ int x; int y; }p[MAX_N]; double walk(int i, int j){ double l = sqrt((double)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (double)(p[i].y - p[j].y) * (p[i].y - p[j].y)); return l * 60 / 10000.0; } double subway(int i, int j){ double l = sqrt((double)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (double)(p[i].y - p[j].y) * (p[i].y - p[j].y)); return l * 60.0 / 40000.0; } void solve(){ for(int k = 1; k <= n; k++){ for(int i = 1;i <= n; i++){ for(int j = 1;j <= n; j++){ G[i][j] = min(G[i][j], G[i][k] + G[k][j]); } } } } int main(){ //freopen("in.cpp", "r", stdin); scanf("%d%d%d%d", &p[1].x, &p[1].y, &p[2].x, &p[2].y); G[1][2] = G[2][1] = walk(1, 2); int j = 0;n = 3; int a, b; while(scanf("%d%d",&a,&b) != EOF){ if(a == -1 && b == -1) j = 0; else{ p[n].x = a, p[n].y = b; for(int i = 1;i < n - j; i++){ G[i][n] = G[n][i] = walk(i,n); } for(int i = n-j; i < n; i++){ G[i][n] = G[n][i] = subway(i,n); } j = 1, n++; } } n--; solve(); printf("%.0f\n", G[1][2]); return 0; }
