首页 > 代码库 > HDU - 1385 Minimum Transport Cost(floyd+字典序)
HDU - 1385 Minimum Transport Cost(floyd+字典序)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1385
题意：给出一个邻接矩阵（对应位置的值代表两个顶点之间的花费），并且到达另外一个位置还要加上那个位置对应的额外花费。
然后求出最少的花费和起点到终点的路径（如果两条路径花费一样，求出字典序最小的）
求任意两点间的最小花费，一般都采用Floyd。Floyd就是一个简单的dp思想，在用Floyd的时候记录一下路径就可以了。
这里要求字典序，可以在路径相等的时候再次进行判断一下，取小的顺序。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int INF=0x3f3f3f3f; 5 const int N=1111; 6 int dp[N][N],path[N][N],c[N]; 7 int n; 8 9 void floyd(){10 //k代表转折点 11 for(int k=1;k<=n;k++){12 for(int i=1;i<=n;i++){13 for(int j=1;j<=n;j++){14 if(dp[i][j]>dp[i][k]+dp[k][j]+c[k])15 {16 dp[i][j]=dp[i][k]+dp[k][j]+c[k];17 path[i][j]=path[i][k]; 18 }19 else if(dp[i][j]==dp[i][k]+dp[k][j]+c[k])20 {21 if(path[i][j]>path[i][k]){22 path[i][j]=path[i][k];23 dp[i][j]=dp[i][k]+dp[k][j]+c[k];24 }25 }26 }27 }28 }29 30 }31 32 void print_path(int s,int t){33 if(s==t) return;34 printf("-->%d",path[s][t]);35 int k=path[s][t];36 print_path(k,t);37 }38 39 int main(){40 int s,t;41 42 while(cin>>n&&n!=0)43 {44 for(int i=1;i<=n;i++)45 {46 for(int j=1;j<=n;j++)47 { 48 path[i][j]=j;49 scanf("%d",&dp[i][j]);50 if(dp[i][j]==-1) dp[i][j]=INF;51 } 52 }53 54 for(int i=1;i<=n;i++) scanf("%d",&c[i]);55 floyd();56 while(cin>>s>>t){57 if(s==-1&&t==-1) break;58 printf("From %d to %d :\n",s,t);59 printf("Path: %d",s);60 print_path(s,t);61 printf("\nTotal cost : %d\n\n",dp[s][t]);62 }63 64 65 }66 return 0;67 }
HDU - 1385 Minimum Transport Cost(floyd+字典序)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。