将车票的使用情况用二进制表示状态，对其进行转移即可。

但是我一开始写的代码是错误的（注释部分），看似思路是正确的，但是暗藏很大的问题。

枚举S，我们要求解的是dp[S][v]，这个是从u转移过来的，不可以写成dp[S|(1<<i)][v]。这也是一次惨痛的教训……

1 #include
2 #include
3 #include
4 using namespace std;
5 const double INF=0x3f3f3f3f;
6 double ans;
7 int n,m,p,a,b;
8 int t[20];
9 int dis[50][50];
10 double dp[1<<10][32];//dp[s][u]表示到达当前u点（使用s的车票）的最小花费 11 12 void solve(){ 13 //memset(dp,0x3f,sizeof(dp));//整型数赋值,不可以 14 for(int i=0;i<(1<<(n+1));i++) 15 fill(dp[i],dp[i]+m+1,INF); 16 dp[0][a]=0; 17 ans=INF; 18 for(int S=0;S<(1<>i)&1)//使用i车票
22 for(int v=1;v<=m;v++) 23 if(dis[u][v]>=0)
24 dp[S][v]=min(dp[S][v],dp[S&~(1<>i)&1)//未使用i车票
39 for(int v=1;v<=m;v++) 40 if(dis[u][v]>=0)
41 dp[S|(1<<i)][v]=min(dp[S|(1<<i)][v],dp[S][u]+dis[u][v]/(double)t[i]);
42 ans=min(ans,dp[S][b]);
43 }
44 }*/
45
46 int main(){
47 while(~scanf("%d%d%d%d%d",&n,&m,&p,&a,&b)){
48 if(n+m+p+a+b==0) break;
49 for(int i=0;i<n;i++) scanf("%d",&t[i]);
50 memset(dis,-1,sizeof(dis));
51 for(int i=0;i<p;i++){
52 int u,v,w;
53 scanf("%d%d%d",&u,&v,&w);
54 dis[u][v]=dis[v][u]=w;
55 }
56 solve();
57 if(ans==INF) printf("Impossible\n");
58 else printf("%.3f\n",ans);
59 }
60 return 0;
61 }