SHARE
TWEET

Untitled

boook Dec 3rd, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*input
  2. 5 5
  3. 0 4
  4. 0 1 1 3
  5. 0 2 2 2
  6. 1 3 1 4
  7. 2 3 2 2
  8. 3 4 2 5
  9. */
  10. #include <iostream>
  11. #include <vector>
  12. #include <utility>
  13. #include <functional>
  14. #include <set>
  15. #include <tuple>
  16.  
  17. #define MAXN (200000+10)
  18. #define MAXM (500000+10)
  19. #define INF (100000000000000000ll)
  20.  
  21. typedef long long int lli;
  22. typedef std::pair<lli,lli> pii;
  23.  
  24. int n, m, s, t;
  25. std::vector<int> nei[MAXN];
  26. std::vector<int> wei[MAXN];
  27. std::vector<int> dan[MAXN];
  28. lli sd[MAXN]; // shortest distance
  29.  
  30.  
  31.  
  32. bool visited[MAXN];
  33. inline void init_visited(){
  34.     for(int i = 0; i < n; ++i) visited[i] = false;
  35. }
  36.  
  37. bool reachable(int from, const int &allowed_danger){
  38.     // DFS
  39.     if(visited[from]) return false;
  40.     visited[from] = true;
  41.     for(size_t i = 0; i < nei[from].size(); ++i){
  42.         if(dan[from][i] > allowed_danger) continue;
  43.         if(nei[from][i] == t) return true;
  44.         if(reachable(nei[from][i], allowed_danger)) return true;
  45.     }
  46.     return false;
  47. }
  48.  
  49.  
  50. int main(){
  51.     std::ios_base::sync_with_stdio(false);
  52.     std::cin.tie(0);
  53.  
  54.     std::cin >> n >> m >> s >> t;
  55.  
  56.     for(int i = 0; i < m; ++i){
  57.         int x, y, d, l;
  58.         std::cin >> x >> y >> d >> l;
  59.         nei[x].push_back(y);
  60.         wei[x].push_back(d);
  61.         dan[x].push_back(l);
  62.         nei[y].push_back(x);
  63.         wei[y].push_back(d);
  64.         dan[y].push_back(l);
  65.     }
  66.  
  67.    
  68.     int L = 1000000000;
  69.     for (int i = 29; i >= 0; -- i) {
  70.         int to = L - (1ll << i);
  71.         init_visited();
  72.         if (reachable(s, to)) L = to;
  73.     }
  74.  
  75.     init_visited();
  76.     std::set<pii> upcoming; // first: distance; second: vertex index
  77.     for(int i = 0; i < n; ++i){
  78.         sd[i] = (i == s) ? 0 : INF;
  79.         upcoming.insert(pii(sd[i], i));
  80.     }
  81.  
  82.     while(!upcoming.empty()){
  83.         int v = upcoming.begin()->second;
  84.         if(v == t) break;
  85.         // sd[v] = upcoming.begin()->first;
  86.         upcoming.erase(upcoming.begin());
  87.         // visited[v] = true;
  88.         for(size_t i = 0; i < nei[v].size(); ++i){
  89.             if(dan[v][i] > L) continue;
  90.             int v2 = nei[v][i];
  91.             // if(visited[v2]) continue;
  92.             // relax
  93.             if(sd[v2] > sd[v] + wei[v][i]){
  94.                 upcoming.erase(upcoming.find(pii(sd[v2], v2)));
  95.                 sd[v2] = sd[v] + wei[v][i];
  96.                 upcoming.insert(pii(sd[v2], v2));
  97.             }
  98.         }
  99.     }
  100.  
  101.     std::cout << sd[t] << ' ' << L << '\n';
  102.  
  103.     return 0;
  104. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top