AOJ 1138 - Traveling by Stagecoach

やるだけ．

解法

(どの都市にいるか, 馬券の使用状況)を頂点にしてDijkstra法をする．

コード

#include <cstdio>
#include <vector>
#include <queue>

#define mp std::make_pair

typedef std::pair<int,int> Pair;
typedef std::pair<double,Pair> Q;

const double INF = 1e20;

int N, M, P, A, B;
int T[8];
std::vector<Pair> es[31];
double d[31][1<<8];
std::priority_queue<Q, std::vector<Q>, std::greater<Q>> q;

int main(){
    while(scanf("%d %d %d %d %d", &N, &M, &P, &A, &B), N || M || P || A || B){
        for(int i=1;i<=M;i++){
            es[i].clear();
        }
        
        for(int i=0;i<N;i++){
            scanf("%d", T+i);
        }
        for(int i=0;i<P;i++){
            int x, y, z;
            scanf("%d %d %d", &x, &y, &z);

            es[x].push_back(mp(y, z));
            es[y].push_back(mp(x, z));
        }

        for(int i=1;i<=M;i++){
            for(int j=0;j<1<<N;j++){
                d[i][j] = INF;
            }
        }
        d[A][0] = 0.0;
        q.push(mp(0.0, mp(A, 0)));

        while(!q.empty()){
            Q q_ = q.top(); q.pop();
            double cost = q_.first;
            int u = q_.second.first, horse = q_.second.second;

            if(cost > d[u][horse]){continue;}

            for(auto e : es[u]){
                for(int i=0;i<N;i++){
                    if(horse >> i & 1){continue;}

                    int n_horse = horse | (1 << i);
                    if(d[e.first][n_horse] > d[u][horse] + 1. * e.second / T[i]){
                        d[e.first][n_horse] = d[u][horse] + 1. * e.second / T[i];
                        q.push(mp(d[e.first][n_horse], mp(e.first, n_horse)));
                    }
                }
            }
        }

        double res = 1e20;
        for(int i=0;i<1<<N;i++){
            res = std::min(res, d[B][i]);
        }

        if(res < INF){
            printf("%.6f\n", res);
        }else{
            puts("Impossible");
        }
    }
}