状态压缩DP 之 poj 2686

第一次做状态压缩DP，之前敲了一个 “旅行商问题” ，对状态压缩DP，有了一定了解，对此题的理解和解决有很大的帮助。

//  [4/29/2014 Sjm]
/*
 
状态压缩： 针对集合的DP。
 
题意： 
旅行家从 a 出发，此时有 S 张车票，为到达 b，求花费最短的时间。
 
分析： 
假设"在 v 点时，旅行商有 S 张票"，
每到达与 a 相邻的国家，需要用掉一张车票i，所到达的国家设为 u，
此时"在 u 点时， 旅行商有 S{i} 张票"，
再到达与 u 相邻的国家，以此类推.....直至到达 b 国家。
 
总结：
在分析中可以看到状态的转换：
     "在 v 点时，旅行商有 S 张票"  ----->  在 u 点时， 旅行商有 S{i} 张票
而转移的开销是： （两点间距离）/ （马匹的数目）。
（可以将上述过程看成建图过程，状态即顶点，转移即边，转移的开销即边的权值）
由于 S(即车票)是集合，故而考虑状态压缩DP解决。
 
综上：
状态：
dp[S][v] := 当此时所到达点为 v并且 所剩票数为 S 时，所需要的最小花费
决策：
dp[S & ~(1<<i)][u] = min(dp[S & ~(1<<i)][u], dp[S][v] + (double)d[v][u] / myT[i])
 
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAX_N = 8, MAX_M = 30, INF = 0x3f3f3f3f;

int n, m, p, a, b;
int myT[MAX_N];  // 马匹数
int d[MAX_M][MAX_M];  // 各国家间道路的距离（-1表示没有道路）
double dp[1 << MAX_N][MAX_M];

void Solve()
{
    double ans = 1.0 * INF;
    for (int i = 0; i < 1 << n; i++)
        fill(dp[i], dp[i] + m, INF);
    dp[(1 << n) - 1][a - 1] = 0;
    for (int S = (1 << n) - 1; S >= 0; S--) {
        ans = min(ans, dp[S][b - 1]);
        for (int v = 0; v < m; v++) {
            for (int i = 0; i < n; i++) {
                if (S >> i & 1) {
                    for (int u = 0; u < m; u++) {
                        if (d[v][u] >= 0) {
                            // 使用车票 i, 从 v 移动到 u。
                            dp[S & ~(1 << i)][u] = min(dp[S & ~(1 << i)][u], dp[S][v] + (double)d[v][u] / myT[i]);
                        }
                    }
                }
            }
        }
    }
    if (INF == ans) printf("Impossible
");
    else printf("%.3f
", ans);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    while (scanf("%d %d %d %d %d", &n, &m, &p, &a, &b) && (n || m || p || a || b)) {
        for (int i = 0; i < n; i++)
            scanf("%d", &myT[i]);
        memset(d, -1, sizeof(d));
        for (int i = 0; i < p; i++) {
            int x, y, z;
            scanf("%d %d %d", &x, &y, &z);
            d[x-1][y-1] = d[y-1][x-1] = z;
        }
        Solve();
    }
    return 0;
}