POJ.3169 Layout

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

2.Idea
This problem is a special case of "Linear programming", which can be solved by graph shortest path problem. Here, Bellman-Ford method is used.

3.Source

 #define MAX_ML 10004  
 #define MAX_MD 10004  
 #define MAX_N 1003  
 int N, ML, MD;  
 int AL[MAX_ML], BL[MAX_ML], DL[MAX_ML];  
 int AD[MAX_MD], BD[MAX_MD], DD[MAX_MD];  
 int d[MAX_N];  
 void solve()  
 {  
      fill(d, d + N, INF);  
      d[0] = 0;  
      for (int k = 0; k < N; k++) {  
           for (int i = 0; i + 1 < N; i++) {  
                if (d[i + 1] < INF) d[i] = min(d[i], d[i + 1]);  
           }  
           for (int i = 0; i < ML; i++) {  
                if (d[AL[i] - 1] < INF) d[BL[i] - 1] = min(d[BL[i] - 1], d[AL[i] - 1] + DL[i]);  
           }  
           for (int i = 0; i < MD; i++) {  
                if (d[BD[i] - 1] < INF) d[AD[i] - 1] = min(d[AD[i] - 1], d[BD[i] - 1] - DD[i]);  
           }  
      }  
      int res = d[N - 1];  
      if(d[0] < 0) {  
           res = -1;  
      }  
      else if (res == INF) {  
           res = -2;  
      }  
      cout << res << endl;  
 }  
 int main()  
 {  
      cin >> N >> ML >> MD;  
      for (int i = 0; i < ML; i++) {  
           cin >> AL[i] >> BL[i] >> DL[i];  
      }  
      for (int i = 0; i < MD; i++) {  
           cin >> AD[i] >> BD[i] >> DD[i];  
      }  
      solve();  
      return 0;  
 }