ZOJ2027 Travelling Fee 动态规划 floyd

题意：给定一个图，求出两点之间的最短路，但是这个最短路是在一条路径上的某条最贵的边能够忽略的情况下的最小值。

分析：直接求出一条最短路再减去这条最短路中的最大值的做法是错误的。例如：如果A-B存在一条(2, 2, 2, 2, 2)的总长为10的路，减去最大值之后是8，存在另外一条路径(1, 8, 2)，总长为11，但是减去最大的8之后就是3了，因此这里要用到动态规划来解。设dp[0][i][j]表示从i到j不使用免费权的最短路径,dp[1][i][j]表示使用免费权的最短路径，则有动态方程：
dp[1][i][j] = min(dp[0][i][k] + dp[1][k][j], dp[1][i][k] + dp[0][k][j]); 
初始化只有直接相邻的节点有dp[1][a][b] = 0, 通过动态规划求出最优解。为什么设这个状态能够求得最优解，因为最终的解一定是由各个子最优状态组合得到的，有边界条件又能够计算出任何一个状态，所以能够得到最后的结果。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <string>
using namespace std;

int N, idx;
int dp[2][205][205];
map<string, int>mp;

void floyd() {
    for (int k = 0; k < idx; ++k) {
        for (int i = 0; i < idx; ++i) {
            if (dp[0][i][k] == -1 || i == k) continue;
            for (int j = 0; j < idx; ++j) {
                if (dp[0][k][j] == -1 || j == k) continue;
                if (dp[0][i][j] == -1) {
                    dp[0][i][j] = dp[0][i][k] + dp[0][k][j];
                }
                else if (dp[0][i][j] > dp[0][i][k] + dp[0][k][j]) {
                    dp[0][i][j] = dp[0][i][k] + dp[0][k][j];
                }
            }
        }
    }
    
    for (int k = 0; k < idx; ++k) {
        for (int i = 0; i < idx; ++i) {
            if (dp[0][i][k] == -1 || i == k) continue;
            for (int j = 0; j < idx; ++j) {
                if (dp[0][k][j] == -1 || j == k) continue;
                if (dp[0][i][j] == -1) continue;
                if (dp[1][i][k] != -1) {
                    if (dp[1][i][j] == -1) {
                        dp[1][i][j] = dp[1][i][k] + dp[0][k][j];
                    } else {
                        dp[1][i][j] = min(dp[1][i][j], dp[1][i][k] + dp[0][k][j]);
                    }
                }
                if (dp[1][k][j] != -1) {
                    if (dp[1][i][j] == -1) {
                        dp[1][i][j] = dp[0][i][k] + dp[1][k][j];
                    } else {
                        dp[1][i][j] = min(dp[1][i][j], dp[0][i][k] + dp[1][k][j]);    
                    }
                }
            }
        }
    }
}

int main() {
    string a, b, sta, end;
    int ct;
    while (cin >> sta >> end) {
        memset(dp, 0xff, sizeof (dp));
        idx = 0;
        mp.clear();
        cin >> N;
        for (int i = 0; i < N; ++i) {
            cin >> a >> b >> ct;
            if (mp.count(a) == 0) {
                mp[a] = idx++;
            }
            if (mp.count(b) == 0) {
                mp[b] = idx++;
            } // 由于题目保证有解，因此只加入边上所涉及的点就可以了
            dp[0][mp[a]][mp[b]] = ct;
            dp[1][mp[a]][mp[b]] = 0; // 只有直接的边才能够被免费处理 
        }
        floyd();
        printf("%d\n", dp[1][mp[sta]][mp[end]]);
    }
    return 0;
}