DAG求最短路–TSP变形–状压dp

DAG状压dp的一种

题目：

$m$个城市，$n$张车票，第i张车票上的时间是$t_i$， 求从$a$到$b$的最短时间，如果无法到达则输出“impossible”

解法：

考虑状态：“现在在城市$v$，此时还剩下的车票的集合为$S$”这样的状态。从这个状态出发，使用一张车票移动到$i \in S$移动到相邻的城市$u$，就相当于转移到了“在城市$u$，此时还剩下的车票的集合为$S/ { i }$”这个状态。

把这个转移看成一条边，那么边上的花费就是（v-u间道路的长度）/ $t_i$。DAG上的最短路dp就能解。

代码如下：

 int n, m, a, b, p;
 int t[MAXN];
 int d[MAXM][MAXM];
 double dp[1 << 12][MAXM]; void solve() {
     for (int i = 0; i < 1 << n; i++) {
         fill(dp[i], dp[i] + m, INF);
     }
     dp[(1 << n) - 1][a - 1] = 0;
     double res = INF;
     for (int S = (1 << n) - 1; S >= 0; S--) {
         res = min(res, 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) {
                             dp[S & ~(1 << i)][u] =
                                 min(dp[S & ~(1 << i)][u],
                                     dp[S][v] + (double)d[v][u] / t[i]);
                         }
                     }
                 }
             }
         }
     }
     if (res == INF) {
         printf("Impossible\n");
     } else {
         printf("%.3f\n", res);
     }
 } int main() {
 #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
 #endif  // !ONLINE_JUDGE
     while (scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) != EOF) {
         if (p == 0 && m == 0 && n == 0 && a == 0 && b == 0) break;
         MEM(t, 0), MEM(d, 0), MEM(dp, 0);
         REP(i, 0, n - 1) scanf("%d", &t[i]);
         REP(i, 0, MAXM - 1) REP(j, 0, MAXM - 1) d[i][j] = -1;
         REP(i, 1, p) {
             int u = READ(), v = READ(), w = READ();
             u--, v--;
             d[u][v] = d[v][u] = w;
         }
         solve();
     }
     return 0;
 }