boook

Untitled

Dec 3rd, 2019
106
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