首页 > 代码库 > zoj1456 Minimum Transport Cost
zoj1456 Minimum Transport Cost
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1456
题目大意:有N个城市,两个城市之间要么有一条运输路线,要么没有。现在有一些货物需要从一个城市运往另一个城市。运输费用包含两部分:通过两个城市之间运输线路的费用,以及通过一个城市时的纳税(起点城市和目标城市除外)。要求输出费用最小,并且路径字典需序最小的线路。
所谓字典序就是,如果有1-->2-->和1-->3两条路可选当输出1-->2-->3。
这题的关键是怎么在最小费用路线不止一条情况下保存字典序最小的路径。
path[a][b]始终保存从a--->b的第二个节点。
floyd算法:
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; #define maxn 1002 #define MM 1000000 int n; int map[maxn][maxn]; int b[maxn]; int path[maxn][maxn]; //保存路径 int tax[maxn]; void init() { int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { path[i][j]=j; } } void floyd() { int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) { if(map[i][k]==MM) //小小的优化 continue; for(j=1;j<=n;j++) if(map[i][j]>map[i][k]+map[k][j]+tax[k]) { map[i][j]=map[i][k]+map[k][j]+tax[k]; path[i][j]=path[i][k]; } else if(map[i][j]==map[i][k]+map[k][j]+tax[k]) //避免漏掉字典序更小的 { path[i][j]=min(path[i][j],path[i][k]); } } } int main() { int len,u,v; while(scanf("%d",&n)!=EOF && n) { init(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&map[i][j]); if(map[i][j]==-1) map[i][j]=MM; } for(int i=1;i<=n;i++) scanf("%d",&tax[i]); floyd(); while(1) { scanf("%d%d",&u,&v); if(v+u==-2) break; printf("From %d to %d :\n",u,v); int tmp=u; printf("Path: %d",u); while(tmp!=v) { printf("-->%d",path[tmp][v]); tmp=path[tmp][v]; } cout<<endl; cout<<"Total cost : "<<map[u][v]<<endl<<endl; //注意格式 } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。