AOJ 2200 Mr. Rito Post Office（Floyd+单调DP）

单调DP）"/>

AOJ 2200 Mr. Rito Post Office（Floyd+单调DP）

【题目链接】 .jsp?id=2200

【题目大意】

　　一张图中有陆路和水路，水路必须要有船才能走，当船开到x点时就会停在x点
　　一开始人和船都在1点，问按给出顺序访问一些点需要的最短时间

【题解】

　　利用floyd可以得出只走陆路和只走水路时两点间的最短路
　　dp[i][j]表示走到了第i个需要访问的村庄，船停在j点的最短路，然后顺序dp更新状态即可

【代码】

#include <cstdio>
#include <algorithm>
#include <cstring> 
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
int n,m,q,x,y,z,d[1010]; char c;
int dl[210][210],ds[210][210],dp[1010][210];
int main(){while(~scanf("%d%d",&n,&m),n+m){rep(i,n)rep(j,n)ds[i][j]=dl[i][j]=i==j?0:INF;rep(i,m){scanf("%d%d%d %c",&x,&y,&z,&c);if(c=='S')ds[x][y]=ds[y][x]=min(ds[x][y],z);else dl[x][y]=dl[y][x]=min(dl[x][y],z);}scanf("%d",&q);rep(i,q)scanf("%d",d+i);rep(k,n)rep(i,n)rep(j,n){ds[i][j]=min(ds[i][j],ds[i][k]+ds[k][j]);dl[i][j]=min(dl[i][j],dl[i][k]+dl[k][j]);}memset(dp,INF,sizeof(dp));dp[1][d[1]]=0;rep(i,q)rep(j,n){dp[i][j]=min(dp[i][j],dp[i-1][j]+dl[d[i-1]][d[i]]);rep(k,n)dp[i][k]=min((LL)dp[i][k],(LL)dp[i-1][j]+dl[d[i-1]][j]+ds[j][k]+dl[k][d[i]]);  }printf("%d\n",*min_element(dp[q],dp[q]+n+1));}return 0;
}

转载于:.html