AOJ 1138 Traveling by Stagecoach

問題

Traveling by Stagecoach | Aizu Online Judge

解法

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;
}