POJ.2686 Traveling by Stagecoach

1.Problem
http://poj.org/problem?id=2686

2.Idea
Bit DP.

3.Source

 #define MAX_N 8  
 #define MAX_M 30  
 int n, m, a, b, p;  
 int t[MAX_N];  
 int d[MAX_M][MAX_M];  
 double dp[1 << MAX_N][MAX_M];  
 void solve()  
 {  
      for (int i = 0; i < 1 << n; i++)   
           fill(dp[i], dp[i] + m, INF);  
      dp[(1 << n) - 1][a - 1] = 0;  
      double res = INF;  
      for (int S = (1 << n) - 1; S >= 0; S--) {  
           res = min(res, dp[S][b - 1]);  
           for (int v = 0; v < m; v++) {  
                for (int i = 0; i < n; i++) {  
                     if (S >> i & 1) {  
                          for (int u = 0; u < m; u++) {  
                               if (d[v][u] >= 0) {  
                                    dp[S & ~(1 << i)][u] = min(dp[S & ~(1 << i)][u], dp[S][v] + (double)d[v][u] / t[i]);  
                               }  
                          }  
                     }  
                }  
           }  
      }  
      if (res == INF) {  
           cout << "Impossible" << endl;  
      }  
      else {  
           cout << fixed << std::setprecision(6) << res << endl;  
      }  
 }  
 int main()  
 {  
      while (scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) > 0) {  
           if (n + m + p + a + b == 0) break;  
           for (int i = 0; i < n; i++) {  
                scanf("%d", &t[i]);  
           }  
           for (int i = 0; i < p; i++) {  
                int x, y, g;  
                scanf("%d%d%d", &x, &y, &g);  
                x--;  
                y--;  
                d[x][y] = d[y][x] = g;  
           }  
           solve();  
      }  
      return 0;  
 }