题目大概是给一张有向图,有n张票,每张票只能使用一次,使用一张票就能用pi匹马拉着走过图上的一条边,走过去花的时间是边权/pi,问从a点走到b点的最少时间是多少。
用dp[u][S]表示当前在u点且用过的票集合是S的最少时间,丢进SPFA更新。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF 1e8
#define MAXN 33
#define MAXM 33*33
struct Edge{
int u,v,next;
double w;
}edge[MAXM];
int NE,head[MAXN];
void addEdge(int u,int v,double w){
edge[NE].u=u; edge[NE].v=v; edge[NE].w=w;
edge[NE].next=head[u]; head[u]=NE++;
}
struct Node{
int u,S;
Node(int _u,int _S):u(_u),S(_S){}
};
int n,m,t[];
double d[][<<];
bool vis[][<<];
void SPFA(int vs){
memset(vis,,sizeof(vis));
vis[vs][]=;
for(int i=; i<=m; ++i){
for(int j=; j<(<<n); ++j) d[i][j]=INF;
}
d[vs][]=;
queue<Node> que;
que.push(Node(vs,));
while(!que.empty()){
Node nd=que.front(); que.pop();
int u=nd.u,S=nd.S;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
for(int j=; j<n; ++j){
if((S>>j)&) continue;
if(d[v][S^(<<j)]>d[u][S]+edge[i].w/t[j]){
d[v][S^(<<j)]=d[u][S]+edge[i].w/t[j];
if(!vis[v][S^(<<j)]){
vis[v][S^(<<j)]=;
que.push(Node(v,S^(<<j)));
}
}
}
}
vis[u][S]=;
}
}
int main(){
int p,vs,vt,a,b;
double c;
while(~scanf("%d%d%d%d%d",&n,&m,&p,&vs,&vt) && (n||m||p||vs||vt)){
NE=;
memset(head,-,sizeof(head));
for(int i=; i<n; ++i) scanf("%d",t+i);
while(p--){
scanf("%d%d%lf",&a,&b,&c);
addEdge(a,b,c); addEdge(b,a,c);
}
SPFA(vs);
double res=INF;
for(int i=; i<(<<n); ++i){
res=min(res,d[vt][i]);
}
if(res==INF) puts("Impossible");
else printf("%f\n",res);
}
return ;
}