ZOJ1232 Adventure of Super Mario floyd+DP

题意：给定N个点求1-N的最短路，所加的附加条件就是这N个点前A个点为村庄，后B个点为城堡。马里奥用一双靴子，能够在一定距离（L）内花0时间进行穿梭，且只有K次机会，在这种情况下，求解一个最短路。

分析：首先对于如何花费这K次机会是一个动态规划的问题，因此我们需要计算出哪些边允许我们进行无代价的穿梭，由于题目还给定了穿梭只能够从某一点开始/结束，因此必须保证某一路径总长度少于L并且题目中还有一个约束条件要求该路径中间不应该有城堡，因为城堡中有陷阱不能够在穿梭的途中有陷阱。而floyd算法能够很好的就算出哪些路径能够穿梭。

解法：首先通过floyd算法从1开始枚举中间点，那么由于前A个节点时村庄，路径中就允许村庄存在，因此在有这些点在更新的时候只要发现任意两点之间的最短距离少于L的话，那么起点和终点之间就一定能够穿梭。而当后面使用城堡来更新最短路的时候就没有这个性质了，所有得到的最短路都不满足中间无城堡这个条件。
　　得到能够穿梭的点对之后，就开始进行动态规划：设dp[i][k]表示从1走到i点使用k次穿梭机会所花的最短时间（单位时间行走单位距离，所以距离和时间值相等）那么有动态规划方程：
　　dp[i][k] = min( dp[j][k-1], dp[j][k] ) 当<i,j>能够穿梭，否则只有后面一项，最后的结果为dp[A+B][K]。

代码如下：

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

int dist[105][105];
int dp[105][15];
bool fly[105][105];
int A, B, M, L, K;


void DP(int N) {
    for (int i = 1; i <= N; ++i) {
        dp[i][0] = dist[1][i];    
    }
    for (int i = 0; i <= K; ++i) {
        dp[1][i] = 0;
    }
    for (int i = 2; i <= N; ++i) { // 枚举从1走到的第i点
        for (int k = 1; k <= K; ++k) { // 枚举这一过程使用了多少次神奇靴子
            int Min = 0x3f3f3f3f;
            for (int j = 1; j < i; ++j) { // 枚举通过中间哪一点走过来
                if (fly[j][i]) {
                    Min = min(Min, dp[j][k-1]);
                }
                Min = min(Min, dp[j][k] + dist[j][i]);
            }
            dp[i][k] = Min;
        }
    }
}

void floyd(int N) {
    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    if (k <= A && dist[i][j] <= L) {
                        fly[i][j] = fly[j][i] = true;
                    }
                    // 由于枚举的中间节点的k是从1开始的，上面的k<=A表示用来作
                    // 作为中间跳板的节点都是村庄，所以只要满足小于L的条件即可
                }
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int a, b, c;
        memset(fly, 0, sizeof (fly));
        memset(dist, 0x3f, sizeof (dist));
        cin >> A >> B >> M >> L >> K;
        for (int i = 0; i < M; ++i) {
            cin >> a >> b >> c;
            dist[a][b] = dist[b][a] = c;
            if (c <= L) {
                fly[a][b] = fly[a][b] = true;
            }
        }
        floyd(A+B);
        DP(A+B);
        cout << dp[A+B][K] << endl;
    }
    return 0;    
}