fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = 0x3f3f3f3f3f3f3f3f;
  17. const int MAX_N = 2e5;
  18. const int MAX_M = 3e5;
  19.  
  20. struct Disjoint_Set_Union{
  21.     int leader[MAX_N + 5], rnk[MAX_N + 5];
  22.  
  23.     void build(int n){
  24.         FOR(i, 1, n){
  25.             leader[i] = i;
  26.             rnk[i] = 1;
  27.         }
  28.     }
  29.  
  30.     int get(int u){
  31.         if(u == leader[u]) return u;
  32.         return leader[u] = get(leader[u]);
  33.     }
  34.  
  35.     void unite(int u, int v){
  36.         int x = get(u), y = get(v);
  37.  
  38.         if(x == y) return;
  39.         if(rnk[x] < rnk[y]) swap(x, y);
  40.  
  41.         rnk[x] += rnk[y];
  42.         leader[y] = leader[x];
  43.     }
  44. }dsu;
  45.  
  46. struct Triple{
  47.     int fi, sec, thr;
  48.  
  49.     Triple(int _fi = 0, int _sec = 0, int _thr = 0){
  50.         fi = _fi;
  51.         sec = _sec;
  52.         thr = _thr;
  53.     }
  54.  
  55.     bool operator < (const Triple &other) const{
  56.         return fi < other.fi;
  57.     }
  58. };
  59.  
  60. vector<Triple> g[MAX_N + 5];
  61. Triple edges[MAX_M + 5];
  62. int dist[MAX_N + 5];
  63. int n, m;
  64.  
  65. void Input(){
  66.     cin >> n >> m;
  67.  
  68.     FOR(i, 1, m){
  69.         int u, v, p, w;
  70.         cin >> u >> v >> p >> w;
  71.  
  72.         g[u].pb({v, p, w});
  73.         g[v].pb({u, p, w});
  74.         edges[i] = {p, u, v};
  75.     }
  76. }
  77.  
  78. int Kruskal(){
  79.     sort(edges + 1, edges + m + 1);
  80.     dsu.build(n);
  81.  
  82.     FOR(i, 1, m){
  83.         int u = edges[i].sec, v = edges[i].thr;
  84.         int p = edges[i].fi;
  85.  
  86.         dsu.unite(u, v);
  87.         if(dsu.get(1) == dsu.get(n)) return p;
  88.     }
  89. }
  90.  
  91. int dijkstra(int max_p){
  92.     FOR(i, 1, n) dist[i] = INF;
  93.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  94.  
  95.     pq.push({0, 1});
  96.     dist[1] = 0;
  97.  
  98.     while(sz(pq)){
  99.         int len = pq.top().fi;
  100.         int u = pq.top().sec;
  101.         pq.pop();
  102.  
  103.         if(len > dist[u]) continue;
  104.  
  105.         for(Triple x : g[u]){
  106.             int v = x.fi, p = x.sec, w = x.thr;
  107.             if(p > max_p) continue;
  108.             if(dist[v] > dist[u] + w){
  109.                 dist[v] = dist[u] + w;
  110.                 pq.push({dist[v], v});
  111.             }
  112.         }
  113.     }
  114.  
  115.     return dist[n];
  116. }
  117.  
  118. void Solve(){
  119.     int max_p = Kruskal();
  120.     cout << max_p << " " << dijkstra(max_p);
  121. }
  122.  
  123. signed main(){
  124.     ios_base::sync_with_stdio(0);
  125.     cin.tie(0);
  126.  
  127.     Input();
  128.     Solve();
  129.  
  130.     return 0;
  131. }
  132.  
Success #stdin #stdout 0.01s 17916KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/cjrRMu
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!