首页 > 代码库 > hdu1385 Minimum Transport Cost 字典序最小的最短路径 Floyd
hdu1385 Minimum Transport Cost 字典序最小的最短路径 Floyd
求最短路的算法最有名的是Dijkstra。所以一般拿到题目第一反应就是使用Dijkstra算法。但是此题要求的好几对起点和终点的最短路径。所以用Floyd是最好的选择。因为其他三种最短路的算法都是单源的。
输出字典序最小的路径则需要修改模版。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N =110, INF=1000000;int Map[N][N], dist[N][N], pre[N][N], c[N];//pre存贮i到j路径中j的前一点int n;void floyd(){ int i,j,k; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dist[i][j]=Map[i][j]; pre[i][j]=j; } } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { //if(dist[i][k]==INF||dist[k][j]==INF) continue; int d=dist[i][k]+dist[k][j]+c[k]; if(d<dist[i][j]) { dist[i][j]=d; pre[i][j]=pre[i][k]; } else if(d==dist[i][j]) { if(pre[i][j]>pre[i][k]) pre[i][j]=pre[i][k]; } }}int main(){ //freopen("test.txt","r",stdin); int i,j,k,a,b; while(scanf("%d",&n)!=EOF) { if(!n) break; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&Map[i][j]); if(Map[i][j]<0) Map[i][j]=INF; } for(i=1;i<=n;i++) scanf("%d",&c[i]); while(scanf("%d%d",&a,&b)) { if(a==-1&&b==-1) break; floyd(); printf("From %d to %d :\n",a,b); printf("Path: %d",a); k=a; while(k!=b){printf("-->%d",pre[k][b]);k=pre[k][b];} printf("\n"); printf("Total cost : %d\n",dist[a][b]); printf("\n"); } } return 0;}
下面是Floyd的模版。pre[][]记录的是前驱。上面的记录的是后继。
const int N =1010, INF=0x3f3f3f3f;int Map[N][N], dist[N][N], pre[N][N];//pre存贮i到j路径中j的前一点int n;void floyd(){ int i,j,k; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dist[i][j]=Map[i][j]; pre[i][j]=i; } } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dist[i][k]!=INF&&dist[k][j]!=INF&& dist[i][k]+dist[k][j]<dist[i][j]) { dist[i][j]=dist[i][k]+ dist[k][j]; pre[i][j]=pre[k][j]; }}void init(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) Map[i][j]=INF;}
hdu1385 Minimum Transport Cost 字典序最小的最短路径 Floyd
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。