AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维

最短路径+动态规划+谨慎+思维"/>

AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维

我写了好多注释，一看就能看懂，这个题目我想了6，7个小时，一开始忽略了船的位置和要把船安置的位置一致的情况，补上就对了。

#include <iostream>
using namespace std;
int inf = 0x3f3f3f3f, num[1007], dp[1007][207], L[207][207], S[207][207], N, M, R;
void init()
{for (int i = 1; i <= N; i++){for (int j = 1; j <= N; j++){L[i][j] = inf;S[i][j] = inf;}L[i][i] = 0;S[i][i] = 0;}
}
void input()
{int from, to, cost;char op;for (int i = 1; i <= M; i++){scanf("%d %d %d %c\n", &from, &to, &cost, &op);if (op == 'S'){if (cost < S[from][to]){S[from][to] = cost;}if (cost < S[to][from]){S[to][from] = cost;}}else if (op == 'L'){if (cost < L[from][to]){L[from][to] = cost;}if (cost < L[to][from]){L[to][from] = cost;}}}scanf("%d", &R);for (int i = 1; i <= R; i++){scanf("%d", &num[i]);}
}
void floyd()
{for (int k = 1; k <= N; k++){for (int i = 1; i <= N; i++){for (int j = 1; j <= N; j++){if (L[i][k] != inf && L[k][j] != inf){if (L[i][k] + L[k][j] < L[i][j]){L[i][j] = L[i][k] + L[k][j];}}if (S[i][k] != inf && S[k][j] != inf){if (S[i][k] + S[k][j] < S[i][j]){S[i][j] = S[i][k] + S[k][j];}}}}}
}
void handleNormalLine(int i, int j)
{// dp[i][j]是从num[1]到达num[i]，并且到达num[i]时船在j的最小路径，当i大于1时，dp[i][j]一定与num[i-2]走到num[i-1]时停船的位置有关// 我们需要从num[i-1]走陆路到k，然后走水路到j，把船停在j，之后走陆路从j到num[i]dp[i][j] = inf;for (int k = 1; k <= N; k++){if (k != j){// 从num[i-1]到k的陆路不通，从k到j的水路不通，从j到num[i]的陆路不通，从1到num[i-1]并且停船到k实现不了,那么这种情况不用计算if (L[num[i - 1]][k] == inf || S[k][j] == inf || L[j][num[i]] == inf || dp[i - 1][k] == inf){continue;}if (L[num[i - 1]][k] + S[k][j] + L[j][num[i]] + dp[i - 1][k] < dp[i][j]){dp[i][j] = L[num[i - 1]][k] + S[k][j] + L[j][num[i]] + dp[i - 1][k];}}else{// k和j相等时，就不需要走陆路到k，然后再走水路到j了，直接从num[i-1]走陆路到num[i]即可，因为j==k船已经在j了，不用管船if (L[num[i - 1]][num[i]] == inf || dp[i - 1][k] == inf){continue;}if (L[num[i - 1]][num[i]] + dp[i - 1][k] < dp[i][j]){dp[i][j] = L[num[i - 1]][num[i]] + dp[i - 1][k];}}}
}
void handleFirstLine(int i, int j)
{// i=1时，船就在num[i]，dp[i][j] i=1 代表开船到j，船放在j，然后陆路走回来num[i]// 走水路开船从num[i]到j，然后船停在j，之后从j走陆路回到num[i]，如果num[i]到j的水路，或者j到num[i]的陆路不通，那么这个都无法实现if (S[num[i]][j] == inf || L[j][num[i]] == inf){dp[i][j] = inf;return;}dp[i][j] = S[num[i]][j] + L[j][num[i]];
}
void doDp()
{// 我们用dp[i][j] 代表邮递员从 num[1]按照顺序一个个走到num[i]，即达到邮递员在num[i]且船的位置在j的状态下，最小的消耗for (int i = 1; i <= R; i++){for (int j = 1; j <= N; j++){if (i == 1){handleFirstLine(i, j);}else{handleNormalLine(i, j);}}}
}
int findAns()
{int ans = inf;for (int i = 1; i <= N; i++){if (dp[R][i] < ans){ans = dp[R][i];}}return ans;
}
int main()
{while (true){scanf("%d%d", &N, &M);if (N == 0 && M == 0){break;}init();input();floyd();doDp();printf("%d\n", findAns());}return 0;
}