# BIO 2018 Round 2 Problem 1 - Byway

Feb 14th, 2021
252
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.