ICPC 国内予選2005D Traveling by Stagecoach AOJ 1138

解法：全探索＋ダイクストラ

馬車券を使う順序が重要で、1 <= (馬車券の数) <= 8 であるからこれは明らかに全組み合わせを試せと言ってるようなもん。（8! = 40320のため
全組み合わせのそれぞれについてダイクストラで最短を求めてそのなかで一番小さい値が答え。
通常のダイクストラを拡張して、馬車券を何枚目まで使ったか、という次元を加える。

priority_queueに三つの値を持たせたくて、昔やったことあったような気がして自分のブログを探したら見つかってバリバリ参考にした。↓（もっとスマートな方法ある気がする、、、
intsawadan.hatenablog.com

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
//typedef pair<double, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
//const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


const double INF = 1000000.0;
const int MAX_V = 35;
struct edge{ int to,cost;};
//typedef pair<int,int> P;
typedef pair<int, int> P;
typedef pair<double,P> PP;
int V,N;
//vector<edge> G[MAX_V];
double d[MAX_V][10];
int t[10];
int main(){
    int n,m,p,a,b;
    while(true){
        cin >> n >> m >> p >> a >> b;
        if(n == 0)break;
        V = m; N = n;
        for(int i = 0;i < n;i++) cin >> t[i];
        vector<edge> G[MAX_V];
        for(int i = 0;i < p;i++){
            int x,y,z;
            cin >> x >> y >> z;
            edge tmp = {y,z};
            G[x].push_back(tmp);
            edge tmp2 = {x,z};
            G[y].push_back(tmp2);
        }
        sort(t, t + n); 
        double ans = INF;
        do {
            priority_queue<PP,vector<PP>,greater<PP> > que;
            for(int i = 0;i <= V;i++){
                for(int j = 0;j <= n;j++){
                    d[i][j] = INF;
                }
            }
            d[a][0] = 0.0;
            que.push(PP(0.0,P(a,0)));
            while(!que.empty()){
                PP p = que.top(); que.pop();
                int v = p.second.first;
                if(d[v][p.second.second] < p.first)continue;
                if(p.second.second == n)continue;
                for(int i = 0;i < G[v].size();i++){
                    edge e = G[v][i];
                    if(d[e.to][p.sc.sc+1] > d[v][p.sc.sc] + ((double) e.cost) / ((double)t[p.sc.sc] ) ){
                        d[e.to][p.sc.sc+1] = d[v][p.sc.sc] + ((double) e.cost) / ((double)t[p.sc.sc] ) ;
                        que.push(PP(d[e.to][p.sc.sc+1],P(e.to,p.sc.sc+1)));
                    }
                }
            }
            double tmp = INF;
            for(int i = 0;i <= n;i++) tmp = min(tmp,d[b][i]);
            if(tmp == INF)break;
            if(ans > tmp) ans = tmp;
        } while(next_permutation(t, t + n));
        if(ans == INF){
            cout << "Impossible" << endl;
        }else{
            printf("%.3f\n",ans);
        }
    }
}