状压DP裸题，将({当前车票集合},当前顶点)这样一个二元组当成状态，然后 边权/马匹 当成边长，跑最短路或者DAG上的DP即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double db;
#define INF 2147483647.0
int n,m,K,Sta,End;
int hor[9];
int e,v[1801],first[31],next[1801],w[1801];
void AddEdge(int U,int V,int W)
{
v[++e]=V;
w[e]=W;
next[e]=first[U];
first[U]=e;
}
db f[1<<9][31];
int main()
{
int x,y,z;
while(1)
{
scanf("%d%d%d%d%d",&K,&n,&m,&Sta,&End);
if(!n) break;
memset(first+1,0,sizeof(int)*n);
e=0;
for(int i=0;i<K;++i)
scanf("%d",&hor[i]);
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
for(int i=0;i<(1<<K);++i)
for(int j=1;j<=n;++j)
f[i][j]=INF;
f[(1<<K)-1][Sta]=0.0;
for(int i=(1<<K)-1;i>=0;--i)
for(int j=1;j<=n;++j)
for(int k=0;k<K;++k)
if(i>>k&1)
for(int l=first[j];l;l=next[l])
f[i-(1<<k)][v[l]]=min(f[i-(1<<k)][v[l]],f[i][j]+(db)w[l]/(db)hor[k]);
db ans=INF;
for(int i=0;i<(1<<K);++i)
ans=min(ans,f[i][End]);
if(ans<INF)
printf("%.3f
",ans);
else
puts("Impossible");
}
return 0;
}