首页 > 代码库 > Aizu - 2200 Mr. Rito Post Office
Aizu - 2200 Mr. Rito Post Office
题意：/*你是某个岛国（ACM-ICPC Japan）上的一个苦逼程序员，
你有一个当邮递员的好基友利腾桑遇到麻烦了：
全岛有一些镇子通过水路和旱路相连，走水路必须要用船，在X处下船了船就停在X处。
而且岛上只有一条船，下次想走水路还是得回到X处才行；
两个镇子之间可能有两条以上的水路或旱路；
邮递员必须按照清单上的镇子顺序送快递
（镇子可能重复，并且对于重复的镇子不允许一次性处理，比如ABCB的话B一定要按顺序走两次才行）。*/
思路:弗洛伊德求出弗洛伊德求出陆路，水路任意两点间的最短距离，然后动态规划求解。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<vector>#include<set>#include<queue>#include<string>#include<algorithm>#define MAXSIZE 1005#define LL long long#define INF 0x3f3f3fusing namespace std;int lmap[MAXSIZE][MAXSIZE],smap[MAXSIZE][MAXSIZE],dp[MAXSIZE][MAXSIZE],q[MAXSIZE],n,m;int solve(){ for(int k=1;k<=n;k++) //弗洛伊德求出陆路，水路任意两点间的最短距离 { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { lmap[i][j] = min(lmap[i][j],lmap[i][k]+lmap[k][j]); smap[i][j] = min(smap[i][j],smap[i][k]+smap[k][j]); } } } dp[1][q[1]] = 0; //初始在第一个城市 for(int i=1;i<=m;i++) //现在派送的城市 { for(int j=1;j<=n;j++) //枚举船在那个城市 { dp[i][j] = min(dp[i][j],dp[i-1][j]+lmap[q[i-1]][q[i]]); for(int k=1;k<=n;k++) //枚举把船停到那个城市 { dp[i][k] = min(dp[i][k],dp[i-1][j]+lmap[q[i-1]][j]+smap[j][k]+lmap[k][q[i]]); } } } int minn = INF; for(int i=1;i<=n;i++) { if(minn > dp[m][i]) minn = dp[m][i]; } return minn;}void Init(){ for(int i=0;i<MAXSIZE;i++) { for(int j=0;j<MAXSIZE;j++) { if(i == j) { //dp[i][j] = 0; lmap[i][j] = 0; smap[i][j] = 0; } else { lmap[i][j] = INF; smap[i][j] = INF; } dp[i][j] = INF; } }}int main(){ char op[5]; int u,v,w; while(scanf("%d%d",&n,&m),n+m) { Init(); for(int i=1;i<=m;i++) { scanf("%d%d%d%s",&u,&v,&w,op); if(op[0] == ‘L‘) { lmap[u][v] = lmap[v][u] = min(lmap[u][v],w); } else { smap[u][v] = smap[v][u] = min(smap[u][v],w); } } scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&q[i]); int ans = solve(); printf("%d\n",ans); } return 0;}
Aizu - 2200 Mr. Rito Post Office
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。