传送门 ：http://acm.hdu.edu.cn/showproblem.php?pid=2544
思路 ：模板题，不多说。
AC代码：
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int n,m; int a[105][105]; int d[105]; int v[105]; void dijkstra() { memset(d,INF,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; for(int i=1; i<n; i++) { int x=0; for(int j=1; j<=n; j++) if(!v[j] && (x==0 || d[j]<d[x])) x=j; v[x]=1; for(int y=1; y<=n; y++) if(!v[y]) d[y]=min(d[y],d[x]+a[x][y]); } } int main() { while(cin>>n>>m) { if(n==0 && m==0) break; int x,y,r; memset(a,INF,sizeof(a)); for(int i=0; i<=n; i++) a[i][i]=0; while(m--) { cin>>x>>y>>r; a[x][y]=a[y][x]=min(a[x][y],r); } dijkstra(); cout<<d[n]<<endl; } return 0; }传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2066
思路： 把草儿家存在数组0处，草儿家相邻的城市p 计做a[0][p]=a[p][0]=0; （即草儿去邻近的城市不需要时间），然后将草儿想去的城市存在一个数组里，最后dijkstra求出草儿家到她想要去的其中一个城市的最短时间。
AC代码：
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int n; int a[1010][1010]; int d[1010]; int v[1010]; void dijkstra() { memset(d,INF,sizeof(d)); memset(v,0,sizeof(v)); d[0]=0; for(int i=0; i<n; i++) { int x=-1; for(int j=0; j<=n; j++) if(!v[j] && (x==-1 || d[j]<d[x])) x=j; v[x]=1; for(int y=0; y<=n; y++) if(!v[y]) d[y]=min(d[y],d[x]+a[x][y]); } } int main() { int t,s,k; int x,y,r; while(cin>>t>>s>>k) { int w[1010]; memset(a,INF,sizeof(a)); while(t--) { cin>>x>>y>>r; n=max(n,max(x,y)); a[x][y]=a[y][x]=min(a[x][y],r); } for(int i=0; i<=n; i++) a[i][i]=0; while(s--) { cin>>x; a[0][x]=a[x][0]=0; } for(int i=0; i<k; i++) cin>>w[i]; dijkstra(); int ans=INF; for(int i=0; i<k; i++) { ans=min(ans,d[w[i]]); } cout<<ans<<endl; } return 0; }传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1874
思路：Floyd模板 三个for套上就过了。
AC代码：
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int main() { int n,m; int a[205][205]; while(cin>>n>>m) { memset(a,0x3f3f3f3f,sizeof(a)); for(int i=0; i<=n; i++) a[i][i]=0; int x,y,r; while(m--) { cin>>x>>y>>r; a[x][y]=a[y][x]=min(a[x][y],r); } for(int k=0; k<=n; k++) for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) a[i][j]=min(a[i][j],a[i][k]+a[k][j]); cin>>x>>y; if(a[x][y]==INF) cout<<-1<<endl; else cout<<a[x][y]<<endl; } return 0; }传送门：http://poj.org/problem?id=2387
思路：老牛回家，经典dijkstra模板题，记得判定重边，套板子就可以过
AC代码：
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1005; const int INF=0x3f3f3f3f; int t,n; int a[N][N]; int d[N]; int v[N]; void dijkstra() { memset(d,INF,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; for(int i=1; i<n; i++) { int x=0; for(int j=1; j<=n; j++) if(!v[j] && (x==0 || d[j]<d[x])) x=j; v[x]=1; for(int y=1; y<=n; y++) if(!v[y]) d[y]=min(d[y],d[x]+a[x][y]); } } int main() { cin>>t>>n; int x,y,r; for(int i=1; i<=n; i++) { a[i][i]=0; for(int j=i+1; j<=n; j++) a[i][j]=a[j][i]=INF; } while(t--) { cin>>x>>y>>r; a[x][y]=a[y][x]=min(a[x][y],r);//判定重边 } for(int i=0; i<=n; i++) a[i][i]=0; dijkstra(); cout<<d[n]<<endl; return 0; }传送门：https://www.51nod.com/Challenge/Problem.html#problemId=1649
思路：一个dijkstra小变形，由题意可知，火车或者汽车总有一种可以一步从1->n,所以我们要做的是判断给出的火车始终点有没有可以一步从1直接到n的。 如果没有，那么汽车就可以一步（一小时）到达终点 ，只需把图修改成火车可以走的路径，汽车公路设置为INF，用使用一次dijkstra即可。 如果火车路径有可以一步从1到n的，那么就把火车的路径设置为INF，其他的路径设置为1，同上。详细怎么做看代码。
AC代码：
#include<bits/stdc++.h> using namespace std; const int N = 405; const int INF = 0x3f3f3f3f; int n,m; struct cc { int x,y; } edge[N*N/2]; int a[N][N]; int d[N],v[N]; void dijkstra() { memset(d,INF,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; for(int i=1; i<n; i++) { int x=0; for(int j=1; j<=n; j++) if(!v[j] && (x==0 || d[j]<d[x])) x=j; v[x]=1; for(int y=1; y<=n; y++) if(!v[y]) d[y]=min(d[y],d[x]+a[x][y]); } } int main() { cin>>n>>m; int flag=0; int x,y; for(int i=0; i<m; i++) { cin>>x>>y; if(x>y) swap(x,y); if(x==1 && y==n) flag=1;//火车路径有一步直接从1到的 edge[i].x=x; edge[i].y=y; } if(!flag) //坐火车无法一步直接到n { memset(a,INF,sizeof(a));//先把整张图权设为INF for(int i=0; i<=n; i++) a[i][i]=0; for(int i=0; i<m; i++) //有火车轨道的路径设置为 1 a[edge[i].x][edge[i].y]=a[edge[i].y][edge[i].x]=1; } else //坐汽车无法一步到n { // memset(a,1,sizeof(a)); // memset函数无法将数组内的值全设成 1 不能这样用！！！ for(int i=1; i<=n; i++) //把所有路径全设为 1 { a[i][i]=0; for(int j=i+1; j<=n; j++) a[i][j]=a[j][i]=1; } for(int i=0; i<m; i++)//有火车轨道的路径设置为 INF a[edge[i].x][edge[i].y]=a[edge[i].y][edge[i].x]=INF; } dijkstra(); if(d[n]==INF) cout<<-1<<endl; else cout<<d[n]<<endl; return 0; }传送门：http://poj.org/problem?id=2253
思路：这道题求的是一条可以从1到2的路径，求路径上最大边的最小值。这题可以修改夏dijkstra模板，把原来的 d[y]=min(d[y],d[x]+a[x][y]); 修改为 d[y]=min(d[y],max(d[x],a[x][y])); d数组储存的是从1到达该点所经历的最大边的最小值，不是总长的最小值
注意：POJ里面用 G++ 提交的时候 double 类型要用 %f 输出，不然判定为Wa,用 C++ 提交就可以用 %lf 了，该题最后输出需要两个回车（\n）。
AC代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int N = 205; const int INF = 10000007; int n; double a[N][N],d[N]; bool v[N]; struct zb { int x,y; } cc[N]; double dis(zb a,zb b) { double x=pow(a.x-b.x,2); double y=pow(a.y-b.y,2); return sqrt(x+y); } void dijkstra() { memset(d,0x7f,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; for(int i=1; i<n; i++) { int x=0; for(int j=1; j<=n; j++) if(!v[j] && (x==0 || d[j]<d[x])) x=j; v[x]=1; for(int y=1; y<=n; y++) if(!v[y]) d[y]=min(d[y],max(d[x],a[x][y])); } } int main() { int cases=0; while(cin>>n,n) { cases++; for(int i=1; i<=n; i++) cin>>cc[i].x>>cc[i].y; for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) a[i][j]=a[j][i]=dis(cc[i],cc[j]); } dijkstra(); printf("Scenario #%d\nFrog Distance = %.3f\n\n",cases,d[2]); } return 0; }