题目在此：AOJ 2200
完整翻译：翻译来源
题目大意：
在一些城市中有水路和陆路连接，每一条路都有长度。但是水路必须乘船，且坐船到达某个位置后船必须留在那里，下次坐必须回到该地。现在有m城市要到达，且必须按照指定的顺序，问最小代价。
Tag：
最短路+dp
做法：
预处理出任意两点间只走水路或陆路的最小代价，然后考虑dp。
记状态dp[i][j]代表要到第i个任务所指定的城市且将船扔到j号城市的最小代价。可以考虑两种情况：只走陆地和陆地水路混合走/只走水路。那么转移非常显然：
只走陆地：直接加上陆地最短路即可，船的位置不变。
混合走/只走水路：从当前点走陆地->停船点->新的停船点->走陆地到目的地，船就停到了新的停船点。
但是要特殊处理一下第一个点，因为它可能会先把船停到某个地方，然后再回到初始点，为后面做准备。
复杂度：
O(R*N^2)
code:
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #define RG register #define IL inline #define pi acos(-1.0) #define ll long long #define inf 1e8 using namespace std; int n,m,R; long long land[300][300],water[300][300],dp[1005][300]; int a[1005]; void pre(){ for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ land[i][j]=land[j][i]=inf; water[i][j]=water[j][i]=inf; } for(int i=1;i<=n;i++) land[i][i]=0,water[i][i]=0; } void floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(k==i||k==j||i==j) continue; water[i][j]=min(water[i][j],water[i][k]+water[k][j]); land[i][j]=min(land[i][j],land[i][k]+land[k][j]); } } int main(){ while(1){ scanf("%d%d",&n,&m); if(n==0&&m==0) break; pre(); for(int i=1;i<=m;i++){ int l,r; string str; long long w; scanf("%d%d%lld",&l,&r,&w); cin>>str; if(str=="L") land[l][r]=land[r][l]=min(land[r][l],w); else water[l][r]=water[r][l]=min(water[r][l],w); } floyd(); scanf("%d",&R); for(int i=1;i<=R;i++) for(int j=1;j<=n;j++) dp[i][j]=inf; for(int i=1;i<=R;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) dp[1][i]=water[a[1]][i]+land[i][a[1]];//第一次出发可以将船停到任意处再坐船回到当前目标点 for(int i=2;i<=R;i++)//目的地 for(int j=1;j<=n;j++)//上一次的下船点 for(int type=1;type<=2;type++){ if(type==1) dp[i][j]=min(dp[i][j],land[a[i-1]][a[i]]+dp[i-1][j]);//走陆地 else for(int k=1;k<=n;k++)//新的下船点 dp[i][k]=min(dp[i][k],dp[i-1][j]+land[a[i-1]][j]+water[j][k]+land[k][a[i]]);//走水路 } long long minn=inf; for(int i=1;i<=n;i++) minn=min(minn,dp[R][i]); printf("%lld ",minn); } return 0; }