题意：

一共有m个城市，城市之间有双向路连接，一个人有n张马车票，一张马车票只能走一条路，走一条路的时间为这条路的长度除以使用的马车票上规定的马车数，问这个人从a出发到b最少使用时间。

分析：

状态压缩dp，用dp[i][j]表示到达j城市的最小时间，其中i为剩余车票的集合。集合i使用状态压缩的表示方法。由于剩余车票的集合不断变小，实际上为求DAG最短路问题。

代码：

#include<cstdio>

#include<cmath>

#include<iostream>

#include<cstring>

using namespace std;

int n, m, p, a, b;

const int maxn =1<<10, maxm = 35, INF = 0x3fffffff;

double dp[maxn][maxm];

int dist[maxm][maxm], t[maxm];

int main (void)

{

    while(~scanf("%d%d%d%d%d",&n,&m,&p,&a,&b)&&n+m+p+a+b!=0){

        for(int i = 0; i < n; i++) scanf("%d",&t[i]);

        int x, y, z;

       memset(dist,-1,sizeof(dist));

        for(int i = 0; i < 1<< n; i++){

            fill(dp[i]+1, dp[i] + m+1, INF);

        }

        dp[(1<<n)-1][a] = 0;

        for(int i = 0; i < p; i++){

            scanf("%d%d%d",&x,&y,&z);

            dist[x][y] = z;

            dist[y][x] = z;

        }

        for(int s = (1<<n) - 2; s >=0; s--){

            res = min(res, dp[s][b]);

          for(int j = 1; j <= m; j++ ){

                for(int i = 0; i < n; i++){

                    if(!(s&1<<i)){

                            for(int k = 1; k <= m; k++){

                                if(dist[k][j]>=0){

                                    dp[s][j] = min(dp[s][j],  dp[s|(1<<i)][k] + (double)dist[k][j]/t[i]);

                            }

                        }

                    }

                }

           }

        }

     double res = INF;

     for(int s = (1<<n) - 1; s >=0; s--)

     if(res==INF) printf("Impossible\n");

     else printf("%.6f\n",res);

    }

    return 0;

}