1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <climits> 5 #include <cctype> 6 #include <cmath> 7 #include <string> 8 #include <sstream> 9 #include <iostream>10 #include <algorithm>11 #include <iomanip>12 using namespace std;13 #include <queue>14 #include <stack>15 #include <vector>16 #include <deque>17 #include <set>18 #include <map>19 typedef long long LL;20 typedef long double LD;21 #define INFF 0x3f3f3f3f22 #define INF 213906214323 #define pi acos(-1.0)24 #define lson l, m, rt<<125 #define rson m+1, r, rt<<1|126 typedef pair<int, int> PI;27 typedef pair<int, PI> PP;28 #ifdef _WIN3229 #define LLD "%I64d"30 #else31 #define LLD "%lld"32 #endif33 //#pragma comment(linker, "/STACK:1024000000,1024000000")34 //LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;}35 //inline int read(){char ch=‘ ‘;int ans=0;while(ch<‘0‘ || ch>‘9‘)ch=getchar();while(ch<=‘9‘ && ch>=‘0‘){ans=ans*10+ch-‘0‘;ch=getchar();}return ans;}36 //inline void print(LL x){printf(LLD, x);puts("");}37 //inline void read(int &x){char c = getchar();while(c < ‘0‘) c = getchar();x = c - ‘0‘; c = getchar();while(c >= ‘0‘){x = x * 10 + (c - ‘0‘); c = getchar();}}38 39 int t[15];40 int mp[35][35];41 double dp[1<<10][35];  // 剩下的车票状态  现在在v的最小花费42 int main()43 {44 #ifndef ONLINE_JUDGE45     freopen("in.txt", "r", stdin);46     freopen("out.txt", "w", stdout);47 #endif48     int n, m, p, a, b;49     while(~scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) && (n || m || p || a || b))50     {51         for(int i=0;i<n;i++)52             scanf("%d", &t[i]);53         memset(mp, -1, sizeof(mp));54         while(p--)55         {56             int u, v, w;57             scanf("%d%d%d", &u, &v, &w);58             u--, v--;59             if(mp[u][v]<0)60                 mp[u][v]=mp[v][u]=w;61             else62                 mp[u][v]=mp[v][u]=min(mp[u][v], w);63         }64         memset(dp, 127, sizeof(dp));65         dp[(1<<n)-1][a-1]=0;66         double ans=INF;67         for(int s=(1<<n)-1;s>=0;s--)68         {69             ans=min(ans, dp[s][b-1]);70             for(int v=0;v<m;v++)71                 for(int i=0;i<n;i++)72                     if(s>>i & 1)73                         for(int u=0;u<m;u++)74                             if(mp[v][u]>=0)75                                 dp[s & ~(1<<i)][u]=min(dp[s & ~(1<<i)][u], dp[s][v]+mp[v][u]*1.0/t[i]);76    // 使用车票i , v->u77         }78         if(ans==INF)79             printf("Impossible\n");80         else81             printf("%.3lf\n", ans);82     }83     return 0;84 }