Advertisement
MinhNGUYEN2k4

Untitled

Nov 14th, 2020
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.95 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int int64_t
  3. #define ii pair<int, int>
  4. #define fi first
  5. #define se second
  6. using namespace std;
  7.  
  8. const int MAX = 1e3+6;
  9. const int MX = 1e15;
  10.  
  11. int n, d[4][MAX], m1, m2, st, en, f[5][MAX], vs[5][MAX], dp[MAX][MAX];
  12. std::vector<ii> g[3][MAX];
  13. int res;
  14.  
  15. void Dijkstra(int num){
  16.     for(int i=1; i<=n; i++) d[num][i] = MX;
  17.     priority_queue<ii, vector<ii>, greater<ii> > pq;
  18.     d[num][en] = 0;
  19.     pq.push(ii(0, en));
  20.     while (!pq.empty()){
  21.         int u = pq.top().se, du = pq.top().fi; pq.pop();
  22.         if (du != d[num][u]) continue;
  23.         for(int i=0; i< g[num][u].size() ; i++){
  24.             int v = g[num][u][i].se, uv = g[num][u][i].fi;
  25.             if (du + uv < d[num][v]){
  26.                 d[num][v] = du + uv;
  27.                 pq.push(ii(d[num][v], v));
  28.             }
  29.         }
  30.     }
  31. }
  32.  
  33. void BFS(){
  34.     queue<ii> q;
  35.     q.push(ii(st, 1));
  36.     while (!q.empty()){
  37.         int u = q.front().fi, type = q.front().se; q.pop();
  38.         // cout << u << "\n";
  39.         for(int i=0; i<(int) g[type][u].size(); i++){
  40.             int v = g[type][u][i].se, uv = g[type][u][i].fi;
  41.             if (d[type][v] < d[type][u]){
  42.                 // cout << u << " " << v << "\n";
  43.                 if (vs[u][v]){
  44.                     res = -1;
  45.                     return;
  46.                 }
  47.                 if (f[type][u] + uv > f[3-type][v]){
  48.                     f[3-type][v] = f[type][u] + uv;
  49.                     vs[u][v] = true;
  50.                     q.push(ii(v, 3-type));
  51.                 }
  52.             }
  53.         }
  54.     }
  55. }
  56.  
  57. void DFS(int u, int type){
  58.     vs[type][u] = 1;
  59.     for(int i=0; i<(int)g[type][u].size(); i++){
  60.         int v = g[type][u][i].se;
  61.         if (d[type][v] >= d[type][u]) continue;
  62.         if (vs[3-type][v]==2) continue;
  63.         if (vs[3-type][v]==1) {
  64.             res = -1;
  65.             return;
  66.             continue;
  67.         }
  68.         // if (u==1 && v==4) cout << "SF\n";
  69.         DFS(v, 3-type);
  70.     }
  71.     vs[type][u] = 2;
  72. }
  73.  
  74. int DP(int u, int type){
  75.     if (u == en) return 0;
  76.     if (dp[u][type] != -1) return dp[u][type];
  77.     dp[u][type] = -99999999999;
  78.     // cout << u << " ";
  79.     for(int i=0; i< g[type][u].size(); i++){
  80.         int v = g[type][u][i].se, uv = g[type][u][i].fi;
  81.         if (d[type][v] < d[type][u]){
  82.             dp[u][type] = max(dp[u][type], DP(v, 3-type) + uv);
  83.         }
  84.     }
  85.     return dp[u][type];
  86. }
  87.  
  88. signed main(int argc, char const *argv[])
  89. {
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0); cout.tie(0);
  92.    
  93.     // #ifndef ONLINE_JUDGE
  94.     //     freopen("input.txt","r",stdin);
  95.     // #endif
  96.    
  97.     ios_base::sync_with_stdio(0);
  98.     cin.tie(0); cout.tie(0);
  99.    
  100.     #ifndef ONLINE_JUDGE
  101.         freopen("TOUR.INP","r",stdin);
  102.         freopen("TOUR.OUT","w",stdout);
  103.     #endif
  104.    
  105.     cin >> n >> st >> en;
  106.     cin >> m1;
  107.     for(int i=1; i<=m1; i++){
  108.         int u, v, w;
  109.         cin >> u >> v >> w;
  110.         g[1][u].push_back(ii(w, v));
  111.         g[1][v].push_back(ii(w, u));
  112.     }
  113.     cin >> m2;
  114.     for(int i=1; i<=m2; i++){
  115.         int u, v, w;
  116.         cin >> u >> v >> w;
  117.         g[2][u].push_back(ii(w, v));
  118.         g[2][v].push_back(ii(w, u));
  119.     }
  120.  
  121.     Dijkstra(1);
  122.     Dijkstra(2); // en
  123.  
  124.     // cout << -1;
  125.     // return 0;
  126.     // BFS();
  127.     memset(dp, -1, sizeof dp);
  128.     DFS(st, 1);
  129.     // cout << "XO";
  130.     if (res==-1) {
  131.         cout << res;
  132.         return 0;
  133.     }
  134.     // DP(en, 1);
  135.     // DP(en, 2);
  136.     cout << DP(st, 1);
  137.     // cout << max(f[1][en], f[2][en]);
  138.     return 0;
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement