poj2686 Traveling by Stagecoach

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

int t[10],d[40][40],k,m,n,a,b,u,v,i,j,s;
double f[40][(1<<10)];

int main(){
	while (scanf("%d%d%d%d%d",&k,&m,&n,&a,&b)){
	  if (!(k|m|n|a|b)) break;
	  for (i=0;i<k;i++) scanf("%d",&t[i]);
	  memset(d,0,sizeof(d)); 
	  for (i=1;i<=m;i++)
	    for (j=0;j<(1<<10);j++) f[i][j]=1e9;
	  for (i=1;i<=n;i++){
	  	int x,y,w;
	  	scanf("%d%d%d",&x,&y,&w);
	  	d[x][y]=d[y][x]=w;
	  }
	  f[a][0]=0;  //*
	  for (s=0;s<(1<<k);s++)  //*
	    for (i=0;i<k;i++)
	      if (s&(1<<i)){
	      	int st=s^(1<<i);
	      	for (v=1;v<=m;v++)
	      	  for (u=1;u<=m;u++)
	      	    if (d[u][v]>0)
				  f[v][s]=min(f[v][s],f[u][st]+(double)d[u][v]/t[i]); //*  
			}
	  double ans=1e9;
	  for (s=0;s<(1<<k);s++) ans=min(ans,f[b][s]);
	  if (ans==1e9) printf("Impossible\n"); else printf("%.3f\n",ans);
    }
	return 0;
}