POJ2686--Travelling by Stagecoach

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1111;
double dp[maxn][35];
int g[35][35];
int t[10];
int n, m, p, a, b;

int main() {
    while(scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) && n != 0 && m != 0) {
        for(int i = 0; i < n; i++)
            scanf("%d", &t[i]);
        for(int i = 0; i < m; i++)
            memset(g[i], -1, sizeof(g[i]));
        for(int i = 0; i < p; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            u--, v--;
            g[u][v] = w;
            g[v][u] = w;
        }
        for(int i = 0; i < 1<<n; i++)
            fill(dp[i], dp[i]+m, 100000000.0);
        dp[(1<<n)-1][a-1] = 0.0;
        double ans = 100000000.0;
        for(int S = (1<<n) -1; S >= 0; S--) {
            ans = min(ans, dp[S][b-1]);
            for(int v = 0; v < m; v++) {
                for(int i = 0; i < n; i++) {
                    if(S>>i & 1) {
                        for(int u = 0; u < m; u++) {
                            if(g[v][u] >= 0) {
                                //    i，   v   u
                                dp[S & ~(1<<i)][u] = min(dp[S & ~(1<<i)][u], dp[S][v] + g[v][u]*1.0/t[i]);
                            }
                        }
                    }
                }
            }
        }
        if(ans != 100000000.0) printf("%.3f
", ans);
        else printf("Impossible
");
    }
    return 0;
}