m个城市 n张车票 一个车票用一次 两条路径之间需要走长度除车票上马车数 求城市a到城市b的最快时间 不能到达就输出Impossible
dp[s][v] 现在在城市v, 剩下车票的集合为s。
《挑战程序设计》P195
#include#include #include using namespace std;const int INF = 0x5f5f5f5f;const int M = 30; // citiesconst int N = 8; // ticketsint n, m, p, a, b;int t[N];int d[M][M];double dp[1 << N][M]; // dp[s][v] S:tickets, v:cityvoid 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) { // 如果车票在S中，即还没有使用 for (int u = 0; u < m; ++u) { // 选择一个城市到达 if (d[v][u] >= 0) { // 如果v,u之间有路径，s中减去车票i来到达u 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(){ while (scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) != EOF) { if (n == 0 && m == 0 && p == 0 && a == 0 && b == 0) break; for (int i = 0; i < n; ++i) scanf("%d", t + i); for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) d[i][j] = -1; int x, y, z; for (int i = 0; i < p; ++i) { scanf("%d%d%d", &x, &y, &z); d[y - 1][x - 1] = d[x - 1][y - 1] = z; } solve(); } return 0;}