AOJ 1138 Traveling by Stagecoach
解法
bitDP 的なダイクストラやるだけ。
const int MAXN = 8; const int MAXP = 1000; const int MAXM = 33; const double INF = 1e18; int T[MAXN]; int dist[MAXM][MAXM]; double dp[MAXM][1<<MAXN]; int main() { int n, m, p, a, b; while (cin >> n >> m >> p >> a >> b) { if (m == 0) break; a--; b--; memset(dist, -1, sizeof(dist)); for (int i = 0; i < n; i++) cin >> T[i]; for (int i = 0; i < p; i++) { int x, y, z; cin >> x >> y >> z; x--; y--; dist[x][y] = dist[y][x] = z; } for (int i = 0; i < m; i++) for (int j = 0; j < 1<<n; j++) { dp[i][j] = INF; } dp[a][0] = 0; priority_queue<pair<double, pii> > que; que.push(make_pair(0, pii(a, 0))); while (!que.empty()) { auto queTop = que.top(); que.pop(); pii p = queTop.second; int v = p.first, s = p.second; double d = -queTop.first; if (d > dp[v][s]) continue; for (int i = 0; i < m; i++) if (dist[v][i] != -1) { for (int j = 0; j < n; j++) { if (((s>>j)&1)==0) { double plus = 1.*dist[v][i]/T[j]; double nd = d+plus; int ns = s|(1<<j); if (dp[i][ns] > nd) { dp[i][ns] = nd; que.push(make_pair(-nd, pii(i, ns))); } } } } } double ans = INF; for (int s = 0; s < 1<<n; s++) { ans = min(ans, dp[b][s]); } if (ans == INF) printf("Impossible\n"); else printf("%.10lf\n", ans); } return 0; }