SP1700 TRSTAGE - Traveling by Stagecoach

传送门：https://www.luogu.org/problem/SP1700

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,p,s,z;
 4 int t[100];
 5 int plat[100][100];
 6 double dp[100][1<<10];
 7 int main()
 8 {
 9     while(scanf("%d%d%d%d%d",&n,&m,&p,&s,&z)!=EOF)
10     {
11         if(m==0&&n==0)break;
12         memset(plat,0,sizeof(plat));
13         for(int i=0;i<=m;i++)
14             fill(dp[i],dp[i]+(1<<n)+1,0x3f3f3f3f);
15         for(int i=0;i<n;i++)scanf("%d",&t[i]);
16         for(int i=0;i<p;i++)
17         {
18             int x,y,v;
19             scanf("%d%d%d",&x,&y,&v);
20             plat[x][y]=plat[y][x]=v;
21         }
22         dp[s][(1<<n)-1]=0;//将第一个点并且不用一张车票  1表示没用 0表示用了
23         for(int i=(1<<n)-1;i>=0;i--)//枚举车票的使用状态
24         {
25             for(int u=1;u<=m;u++)//枚举起点
26             {
27                 for(int j=0;j<n;j++)//枚举使用的车票
28                 {
29                     if(i&(1<<j))//如果一张票没有用过
30                     {
31                         for(int v=1;v<=m;v++)//枚举终点
32                         {
33                             if(plat[u][v])//如果可以通达
34                             {
35                                 dp[v][i&~(1<<j)]=min(dp[v][i&~(1<<j)],dp[u][i]+(double)plat[u][v]/t[j]);
　　　　　　　　　　　　　　　　　　　　　　//10001在进行~后就变成01110，用i&~(1<<j)来标记一张票用过了
36                             }
37                         }
38                     }
39                 }
40             }
41         }
42         double ans=0x3f3f3f3f;
43         for(int i=0;i<(1<<n);i++)ans=min(ans,dp[z][i]);
44         if(ans==0x3f3f3f3f)cout<<"Impossible"<<endl;
45         else printf("%.3lf\n",ans);
46     }
47     return 0;
48 }