dp+最短路——Mr. Rito Post Office（Aizu

Rito Post Office（Aizu"/>

dp+最短路——Mr. Rito Post Office（Aizu

dp+最短路

——Mr. Rito Post Office（Aizu - 2200 ）
在一些城市中有水路和陆路连接，每一条路都有长度。但是水路必须乘船，且坐船到达某个位置后船必须留在那里，下次坐必须回到该地。现在有m城市要到达，且必须按照指定的顺序，问最小代价。
Sample Input
3 3
1 2 5 L
1 2 7 S
2 3 11 S
3
1 2 3
5 5
1 2 15 L
2 3 10 L
4 5 7 L
1 3 30 S
3 4 100 S
5
1 3 5 4 1
0 0
Output for the Sample Input
18
269

解析：首先用floyd-warshall算法将每两个点之间的最短陆路和水路路径求出。
再者，（下面万年不会的dp了）dp[i][j]=在第i个城市的时候，将船停靠在j这个时候所需要的最小花费。
转移方程：
1.就是当前一步通过陆路来走
dp[i][j]=min(dp[i][j],dp[i-1][j]+land[d[i-1]][d[i]]);
2.这一种就是中间有使用过水路，并且把船停在了k号位置上，再从陆路走到当前城市。(这里注意水路不是仅仅一步从上一个城市走到当前城市，而是中间有用过水路）
for(int k=1;k<=n;k++){ dp[i][k]=min(dp[i][k] ,
dp[i-1][j]+land[d[i-1]][j]+water[j][k]+land[k][d[i]]); }
3.最后答案是，再最后一个城市的时候，船停在任意一个城市的最小值。
注意点：1.使用LL
2.初始化dp时，第一步虽然你也可以什么都不用走，但是你可以将船放到任意点上，你再走回来哦！
3.这里边双向，并且输入边可能重复，所以取最小的。

#include<cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
long long water[400][400],land[400][400],dp[2000][400];
int n,m,p,a,b,d[2000];
long long c;
char s1,s2;
void floyd()
{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){water[j][k]=min(water[j][k],water[j][i]+water[i][k]);land[j][k]=min(land[j][k],land[j][i]+land[i][k]);}}}
}
int main()
{while(~scanf("%d%d",&n,&m)&&n){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j){water[i][j]=0;land[i][j]=0;continue;}water[i][j]=inf;land[i][j]=inf;}}for(int i=0;i<m;i++){scanf("%d%d%lld%c%c",&a,&b,&c,&s1,&s2);if(s2=='S') {water[a][b]=min(c,water[a][b]);water[b][a]=water[a][b];}else {land[a][b]=min(land[a][b],c);land[b][a]=land[a][b];}}floyd();scanf("%d",&p);for(int i=0;i<p;i++){scanf("%d",&d[i]);}for(int i=0;i<p;i++) for(int j=1;j<=n;j++) dp[i][j]=inf;for(int i=1;i<=n;i++) dp[0][i]=water[d[0]][i]+land[i][d[0]];for(int i=1;i<p;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i][j],dp[i-1][j]+land[d[i-1]][d[i]]);for(int k=1;k<=n;k++){dp[i][k]=min(dp[i][k],dp[i-1][j]+land[d[i-1]][j]+water[j][k]+land[k][d[i]]);}}}long long ans=inf;for(int i=1;i<=n;i++){ans=min(ans,dp[p-1][i]);}printf("%lld\n",ans);}return 0;
}