Advertisement
Guest User

Untitled

a guest
Dec 2nd, 2019
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <functional>
  5. #include <set>
  6. #include <tuple>
  7.  
  8. #define MAXN (200000+10)
  9. #define MAXM (500000+10)
  10. #define INF (100000000000000000ll)
  11.  
  12. typedef long long int lli;
  13. typedef std::pair<lli,lli> pii;
  14.  
  15. int n, m, s, t;
  16. std::vector<int> nei[MAXN];
  17. std::vector<int> wei[MAXN];
  18. std::vector<int> dan[MAXN];
  19. lli sd[MAXN]; // shortest distance
  20.  
  21.  
  22.  
  23. bool visited[MAXN];
  24. inline void init_visited(){
  25.     for(int i = 0; i < n; ++i) visited[i] = false;
  26. }
  27.  
  28. bool reachable(int from, const int &allowed_danger){
  29.     // DFS
  30.     if(from == t) return true;
  31.     if(visited[from]) return false;
  32.     visited[from] = true;
  33.     for(size_t i = 0; i < nei[from].size(); ++i){
  34.         if(dan[from][i] > allowed_danger) continue;
  35.         if(nei[from][i] == t) return true;
  36.         if(reachable(nei[from][i], allowed_danger)) return true;
  37.     }
  38.     return false;
  39. }
  40.  
  41.  
  42. int main(){
  43.     std::ios_base::sync_with_stdio(false);
  44.     std::cin.tie(0);
  45.  
  46.     std::cin >> n >> m >> s >> t;
  47.  
  48.     for(int i = 0; i < m; ++i){
  49.         int x, y, d, l;
  50.         std::cin >> x >> y >> d >> l;
  51.         nei[x].push_back(y);
  52.         wei[x].push_back(d);
  53.         dan[x].push_back(l);
  54.         nei[y].push_back(x);
  55.         wei[y].push_back(d);
  56.         dan[y].push_back(l);
  57.     }
  58.  
  59.     // binary search for the minimal L
  60.     // L in (l,r]
  61.     int L;
  62.     {
  63.         int l = -1, r = 1000000000;
  64.         while(l+1 != r){
  65.             int mid = (l+r+1) / 2;
  66.             init_visited();
  67.             if(reachable(s, mid)) r = mid;
  68.             else                  l = mid;
  69.         }
  70.         L = r;
  71.     }
  72.  
  73.     // calculate shortest path using Dijkstra's
  74.     std::set<pii> upcoming; // first: distance; second: vertex index
  75.     for(int i = 0; i < n; ++i){
  76.         sd[i] = (i == s) ? 0 : INF;
  77.         upcoming.insert(pii(sd[i], i));
  78.     }
  79.  
  80.     while(!upcoming.empty()){
  81.         int v = upcoming.begin()->second;
  82.         if(v == t) break;
  83.         upcoming.erase(upcoming.begin());
  84.         for(size_t i = 0; i < nei[v].size(); ++i){
  85.             if(dan[v][i] > L) continue;
  86.             int v2 = nei[v][i];
  87.             // relax
  88.             if(sd[v2] > sd[v] + wei[v][i]){
  89.                 upcoming.erase(upcoming.find(pii(sd[v2], v2)));
  90.                 sd[v2] = sd[v] + wei[v][i];
  91.                 upcoming.insert(pii(sd[v2], v2));
  92.             }
  93.         }
  94.     }
  95.  
  96.     std::cout << sd[t] << ' ' << L << '\n';
  97.  
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement