Advertisement
erek1e

BIO 2018 Round 2 Problem 1 - Byway

Feb 14th, 2021
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. const long long int LL_MAX = ~0ULL >> 1;
  9.  
  10. int main() {
  11.     int v; cin >> v;
  12.     vector< vector< pair<int, long long> > > g(1+v);
  13.     int x, y; long long t;
  14.     while (cin >> x && cin >> y && cin >> t && x != -1) {
  15.         g[x].emplace_back(y, t);
  16.         g[y].emplace_back(x, t);
  17.     }
  18.  
  19.     vector<long long> dist[2];
  20.     auto shortestPath = [&](int start, int store) {
  21.         dist[store] = vector<long long>(1+v, LL_MAX);
  22.         priority_queue< pair<long long, int>, vector< pair<long long, int> >, greater< pair<long long, int> > > pq;
  23.         vector<bool> seen(1+v);
  24.         dist[store][start] = 0;
  25.         pq.emplace(0, start);
  26.         while (!pq.empty()) {
  27.             int node = pq.top().second;
  28.             pq.pop();
  29.  
  30.             if (seen[node]) continue;
  31.             seen[node] = true;
  32.  
  33.             for (pair<int, long long> child : g[node]) {
  34.                 long long d = dist[store][node] + child.second;
  35.                 if (!seen[child.first] && d < dist[store][child.first]) {
  36.                     dist[store][child.first] = d;
  37.                     pq.emplace(d, child.first);
  38.                 }
  39.             }
  40.         }
  41.     };
  42.  
  43.     shortestPath(1, 0);
  44.     shortestPath(v, 1);
  45.  
  46.     long long minD = LL_MAX;
  47.     for (int node = 1; node <= v; ++node) {
  48.         for (auto [child, w] : g[node]) {
  49.             long long curD = dist[0][node] + w/2 + dist[1][child];
  50.             minD = min(minD, curD);
  51.         }
  52.     }
  53.     cout << minD << endl;
  54.     return 0;
  55. }
  56.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement