首页 > 代码库 > hdoj 1385Minimum Transport Cost
hdoj 1385Minimum Transport Cost
卧槽。。。。最近刷的cf上有最短路，本来想拿这题复习一下。。。。
题意就是在输出最短路的情况下，经过每个节点会增加税收，另外要字典序输出，注意a到b和b到a的权值不同
然后就是处理字典序的问题，当松弛时发现相同值的时候，判断两条路径的字典序
代码
#include "stdio.h"const int MAXN=110;const int INF=10000000;bool vis[MAXN];int pre[MAXN];int cost[MAXN][MAXN],lowcost[MAXN],b1[MAXN];int road[MAXN];using namespace std;int cmp(int a,int b,int c){ int i,len1,len2,j; int p1[MAXN],p2[MAXN]; int cur=a; pre[a]=b; len1=0; while(cur!=-1) { p1[len1++]=cur; cur=pre[cur]; } len2=0; cur=a; pre[a]=c; while(cur!=-1) { p2[len2++]=cur; cur=pre[cur]; } for(i=len1-1,j=len2-1;i>=0&&j>=0;i--,j--) { if(p1[i]>p2[j]) return c; if(p1[i]<p2[j]) return b; } if(i==-1) return b; if(j==-1) return c;}void dijkstra(int beg,int n){ int ans; int k=0; for(int i=0; i<n; i++) { lowcost[i]=cost[beg][i]; vis[i]=false; pre[i]=-1; } for(int j=0; j<n; j++) { int k; int min=INF; for(int i=0; i<n; i++) if(!vis[i]&&lowcost[i]<min) { min=lowcost[i]; k=i; } if(k==-1) break; vis[k]=true; for(int i=0; i<n; i++) { if(cost[k][i]==INF) continue; if(!vis[i]&&lowcost[k]+cost[k][i]+b1[k]<lowcost[i]) { lowcost[i]=lowcost[k]+cost[k][i]+b1[k]; pre[i]=k; } else if(!vis[i]&&lowcost[k]+cost[k][i]+b1[k]==lowcost[i]) pre[i]=cmp(i,pre[i],k); } }}void print(int cur){ if(pre[cur]!=-1) print(pre[cur]); printf("-->%d",cur+1);}int main(){ int n,i,j; int a,b,c; int ans,len; while(scanf("%d",&n)==1,n) { for(i=0; i<n; i++) { for(j=0; j<n; j++) { scanf("%d",&cost[i][j]); if(cost[i][j]==-1) cost[i][j]=INF; } } for(i=0; i<n; i++) scanf("%d",&b1[i]) ; while(scanf("%d%d",&a,&b)==2) { if(a==-1&&b==-1) break; a-=1; b-=1; len=0; dijkstra(a,n); ans=lowcost[b]; printf("From %d to %d :\nPath: %d",a+1,b+1,a+1); if(a!=b) print(b); printf("\n"); printf("Total cost : %d\n\n",ans); } } return 0;}这里有一个小插曲，这题和zoj某题一样，搜索hdoj题号，出来的是floyd和dij上面暴力的解法，搜索zoj题号，出来的是dij+dfs解法，引人深思。。。
hdoj 1385Minimum Transport Cost
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。