fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const ll oo = 2e18;
  7. const int N = 2e5+5;
  8. const int M = 3e5+5;
  9.  
  10. struct Edge {
  11.     int u, v; ll p, w;
  12.     bool operator<(const Edge& b) const {
  13.         return p < b.p;
  14.     }
  15. } edges[M];
  16.  
  17. struct Node {
  18.     int to; ll w;
  19. };
  20.  
  21. int n, m;
  22. ll D[N];
  23. vector<Node> adj[N];
  24.  
  25. int p[N], sz[N];
  26. int find(int u) {
  27.     return (p[u] == u) ? u : (p[u] = find(p[u]));
  28. }
  29.  
  30. void unite(int u, int v) {
  31.     u = find(u), v = find(v);
  32.     if (u == v) return;
  33.     if (sz[u] < sz[v]) swap(u, v);
  34.     p[v] = u;
  35.     sz[u] += sz[v];
  36. }
  37.  
  38. void solve() {
  39.     cin >> n >> m;
  40.     for (int i = 0; i < m; i++)
  41.         cin >> edges[i].u >> edges[i].v >> edges[i].p >> edges[i].w;
  42.     sort(edges, edges + m);
  43.  
  44.     for (int i = 1; i <= n; i++) {
  45.         p[i] = i;
  46.         sz[i] = 1;
  47.     }
  48.  
  49.     ll P = -1;
  50.     for (int i = 0; i < m; i++)  {
  51.         unite(edges[i].u, edges[i].v);
  52.         if (find(1) == find(n)) {
  53.             P = edges[i].p;
  54.             break;
  55.         }
  56.     }
  57.  
  58.     for (int i = 0; i < m; i++)
  59.         if (edges[i].p <= P) {
  60.             adj[edges[i].u].push_back({edges[i].v, edges[i].w});
  61.             adj[edges[i].v].push_back({edges[i].u, edges[i].w});
  62.         } else break;
  63.  
  64.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  65.     for (int i = 1; i <= n; i++) D[i] = oo;
  66.  
  67.     D[1] = 0;
  68.     pq.push({0, 1});
  69.  
  70.     while (!pq.empty()) {
  71.         pair<ll, int> t = pq.top(); pq.pop();
  72.         ll d = t.first; int u = t.second;
  73.         if (d > D[u]) continue;
  74.         if (u == n) break;
  75.         for (Node& e : adj[u]) {
  76.             int v = e.to; ll nd = d + e.w;
  77.             if (D[v] > nd) {
  78.                 D[v] = nd;
  79.                 pq.push({D[v], v});
  80.             }
  81.         }
  82.     }
  83.     cout << P << " " << D[n] << "\n";
  84. }
  85.  
  86. int main() {
  87.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  88.  
  89.     #define TASK "SOTAN"
  90.     if (fopen(TASK".INP", "r")) {
  91.         freopen(TASK".INP", "r", stdin);
  92.         freopen(TASK".OUT", "w", stdout);
  93.     }
  94.  
  95.     int tests = 1; // cin >> tests;
  96.     while (tests--) solve();
  97.  
  98.     #ifndef ONLINE_JUDGE
  99.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  100.     #endif
  101.  
  102.     return 0;
  103. }
Success #stdin #stdout 0.01s 11760KB
comments (?)
stdin
copy 
5 7
1 2 1 1
3 5 1 1
1 3 2 3
2 3 3 1
4 5 1 2
2 4 1 2
2 5 1 3
stdout
copy 
1 4
https://ideone.com/bJnk46
language:
C++14 (gcc 8.3)
created:
7 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!