POJ.3411 Paid Roads

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

2.Idea
bit DP + Bellman-Ford

3.Source

 #define MAX_N 10  
 #define MAX_M 10  
 struct Edge {  
      int a, b, c, p, r;  
 } Edges[MAX_M];  
 int dp[1 << MAX_N][MAX_N];  
 int n, m;  
 int main()  
 {  
      cin >> n >> m;  
      for (int i = 0; i < m; i++) {  
           cin >> Edges[i].a >> Edges[i].b >> Edges[i].c >> Edges[i].p >> Edges[i].r;  
           Edges[i].a--;  
           Edges[i].b--;  
           Edges[i].c--;  
      }  
      for (int i = 0; i < 1 << MAX_N; i++) {  
           fill(dp[i], dp[i] + MAX_N, INF);  
      }  
      dp[1][0] = 0;  
      bool update;  
      while (1) {  
           update = false;  
           for (int _ = 0; _ < n; _++) {  
                for (int i = 0; i < m; i++) {  
                     int a = Edges[i].a, b = Edges[i].b, c = Edges[i].c, p = Edges[i].p, r = Edges[i].r;  
                     for (int S = 0; S < 1 << n; S++) {  
                          if ((S & (1 << a)) && dp[S][a] < INF) {  
                               if (dp[S | (1 << b)][b] > dp[S][a] + r) {  
                                    update = true;  
                                    dp[S | (1 << b)][b] = dp[S][a] + r;  
                               }  
                               if ((S & (1 << c))) {  
                                    if (dp[S | (1 << b)][b] > dp[S][a] + p) {  
                                         update = true;  
                                         dp[S | (1 << b)][b] = dp[S][a] + p;  
                                    }  
                               }  
                          }  
                     }  
                }  
           }  
           if (!update) break;  
      }  
      int ans = INF;  
      for (int S = 0; S < 1 << n; S++) {  
           ans = min(ans, dp[S][n - 1]);  
      }  
      if (ans == INF) {  
           cout << "impossible" << endl;  
      }  
      else {  
           cout << ans << endl;  
      }  
      return 0;  
 }