AOJ 2200 Mr. Rito Post Office Floyd+DP

Rito Post Office Floyd+DP"/>

AOJ 2200 Mr. Rito Post Office Floyd+DP

题目链接
题目是日文的。。。
下面是参考的其他博客中的题目大意：

你有一个当邮递员的好基友利腾桑遇到麻烦了：全岛有一些镇子通过水路和旱路相连，走水路必须要用船，在X处下船了船就停在X处。而且岛上只有一条船，下次想走水路还是得回到X处才行；两个镇子之间可能有两条以上的水路或旱路；邮递员必须按照清单上的镇子顺序送快递（镇子可能重复，并且对于重复的镇子不允许一次性处理，比如ABCB的话B一定要按顺序走两次才行）。
测试数据有多组：
N M
x1 y1 t1 sl1
x2 y2 t2 sl2
…
xM yM tM slM
R
z1 z2 … zR
N (2 ≤ N ≤ 200) 是镇子的数量，M (1 ≤ M ≤ 10000) 是旱路和水路合计的数量。从第2行到第M + 1行是路径的描述，路径连接xi yi两地，路径花费 ti (1 ≤ ti ≤ 1000)时间，sli 为L时表示是旱路，S时表示是水路。可能有两条及以上路径连接两个镇子，并且路径都是双向的。
M + 2行的R是利腾需要去的镇子的数量，M + 3是利腾需要去的镇子的编号。
初始状态利腾和船都在第一个镇子，且肯定有方法达到需要去的镇子。
测试数据为0 0的时候表示终止。
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
18
269

但是，这段翻译其实是有歧义的，初始状态下利腾和船是都在清单上的第一个镇子！！！而不是编号为1的镇子！！！而且题目中的样例第一个要去的镇子还都是编号为1的镇子。。。我已经无法回想起我被这几个字坑了多长时间了。。。都是泪啊。。。

解题思路：
floyd+dp
先用Floyd预处理出单独走陆路map1或水路map2情况下，镇子两两之间的最短路。

d[i][j]表示已经去了清单上的第i个镇子后，船停在镇子编号为j的状态下的最短路
z[i]用于存放清单上第i个要去的镇子
状态转移：
若只走陆路：dp[i][j] = min(dp[i][j], dp[i - 1][j] + map1[z[i - 1]][z[i]]);
若走的过程中有水路：
从当前点走陆地到停船点->走水路到新的停船点->走陆地到目的地，这样船就停到了新的停船点。

核心代码：

for (int i = 1; i <= r; i++) {//第i个目的城市for (int j = 1; j <= n; j++) {//上次停船点if (dp[i - 1][j] == INF) continue;//上次不可能停在编号为j的镇子if ( map1[z[i - 1]][z[i]] != INF) {//陆路可走dp[i][j] = min(dp[i][j], dp[i - 1][j] + map1[z[i - 1]][z[i]]);}for (int k = 1; k <= n; k++) {//本次停船点if (map1[z[i - 1]][j] != INF && map2[j][k] != INF && map1[k][z[i]] != INF) {dp[i][k] = min(dp[i][k], dp[i - 1][j] + map1[z[i - 1]][j] + map2[j][k] + map1[k][z[i]]);}}}
}

AC代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxn 220
#define maxm 1100 //任务数量
#define INF 0x3fffffff
int map1[maxn][maxn];//陆路地图
int map2[maxn][maxn];//水路地图
int dp[maxm][maxn];
int n, m;
int z[maxm];//保存清单上的任务顺序
void init(int x) {//初始化for (int i = 1; i <= x; i++) {for (int j = 1; j <= x; j++) {map1[i][j] = INF; map2[i][j] = INF;}map1[i][i] = 0; map2[i][i] = 0;}
}int main() {while (scanf("%d%d", &n, &m) != EOF) {if (n == 0 && m == 0) break;init(n);//对地图进行初始化int u, v, w; char type;for (int i = 1; i <= m; i++) {scanf("%d%d%d %c", &u, &v, &w, &type);//cin >> u >> v >> w >> type;if (type == 'L') {//陆上map1[u][v] = min(w, map1[u][v]);map1[v][u] = map1[u][v];}else {map2[u][v] = min(w, map2[u][v]);map2[v][u] = map2[u][v];}}//Floyd算法for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (map1[i][k] == INF || map1[k][j] == INF) continue;if (map1[i][j] == INF || map1[i][j] > map1[i][k] + map1[k][j]) {map1[i][j] = map1[i][k] + map1[k][j];}}for (int p = 1; p <= n; p++) {if (map2[i][k] == INF || map2[k][p] == INF) continue;if (map2[i][p] == INF || map2[i][p] > map2[i][k] + map2[k][p]) {map2[i][p] = map2[i][k] + map2[k][p];}}}}int r;scanf("%d", &r);for (int i = 1; i <= r; i++) { scanf("%d", &z[i]); }//初始化for (int i = 0; i <= r; i++) {for (int j = 0; j <= n; j++) {dp[i][j] = INF;}}dp[1][z[1]] = 0;//初始时快递员与船都在清单上的第一个镇子//第一次出发可以先走水路将船停到任意处，再走陆路回到当前目标点for (int i = 1; i <= n; i++)dp[1][i] =min(dp[1][i], map2[z[1]][i] + map1[i][z[1]]);//状态转移for (int i = 2; i <= r; i++) {//第i个目的城市for (int j = 1; j <= n; j++) {//上次停船点if (dp[i - 1][j] == INF) continue;//上次不可能停在编号为j的镇子if (map1[z[i - 1]][z[i]] != INF) {//陆路可走dp[i][j] = min(dp[i][j], dp[i - 1][j] + map1[z[i - 1]][z[i]]);}for (int k = 1; k <= n; k++) {//本次停船点if (map1[z[i - 1]][j] != INF && map2[j][k] != INF && map1[k][z[i]] != INF) {dp[i][k] = min(dp[i][k], dp[i - 1][j] + map1[z[i - 1]][j] + map2[j][k] + map1[k][z[i]]);}}}}int ans = INF;for (int i = 1; i <= n; i++) { ans = min(ans, dp[r][i]); }printf("%d\n", ans);}
}