fork download
copy 
  1. //thanh huyenn ne//
  2. #include<bits/stdc++.h>
  3. #define int long long
  4. using namespace std;
  5. int n, m, a1, a2, a3, ans = -1;
  6. vector<pair<int,int>> p[100001];
  7. vector<pair<int,int>> ytb[100001];
  8. map<pair<int,int>,int> mp;
  9. void nhap() {
  10.     cin >> n >> m;
  11.     for (int i = 1; i <= m; i++) {
  12.         int a, b, c;
  13.         cin >> a >> b >> c;
  14.         if (c > ans) {
  15.             ans = c;
  16.             a1 = a;
  17.             a2 = b;
  18.             a3 = c;
  19.         }
  20.         p[a].push_back({b, c});
  21.         ytb[a].push_back({b, c});
  22.         mp[{a, b}] = c;
  23.     }
  24.     ytb[a1].push_back({a2, a3/2});
  25. }
  26.  
  27. int bfs(int s) {
  28.     vector<int> d(n + 1, LLONG_MAX);
  29.     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
  30.     q.push({0, s});
  31.     d[s] = 0;
  32.     while (!q.empty()) {
  33.         int x = q.top().second;
  34.         int dist_x = q.top().first;
  35.         q.pop();
  36.         if (dist_x > d[x]) continue;
  37.         for (pair<int,int> v : ytb[x]) {
  38.             int cc = v.first;
  39.             int ll = v.second;
  40.             if (d[cc] > d[x] + ll) {
  41.                 d[cc] = d[x] + ll;
  42.                 q.push({d[cc], cc});
  43.             }
  44.         }
  45.     }
  46.     return d[n];
  47. }
  48.  
  49. int dijkstra(int s) {
  50.     vector<int> d(n + 1, LLONG_MAX);
  51.     vector<int> trace(n + 1, -1);
  52.     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
  53.     q.push({0, s});
  54.     d[s] = 0;
  55.     while (!q.empty()) {
  56.         int x = q.top().second;
  57.         int dist_x = q.top().first;
  58.         q.pop();
  59.         if (dist_x > d[x]) continue;
  60.         for (pair<int,int> v : p[x]) {
  61.             int cc = v.first;
  62.             int ll = v.second;
  63.             if (d[cc] > d[x] + ll) {
  64.                 d[cc] = d[x] + ll;
  65.                 trace[cc] = x;
  66.                 q.push({d[cc], cc});
  67.             }
  68.         }
  69.     }
  70.     vector<int> path;
  71.     int curr = n;
  72.     while (curr != -1) {
  73.         path.push_back(curr);
  74.         curr = trace[curr];
  75.     }
  76.     int res = -1;
  77.     reverse(path.begin(), path.end());
  78.     for (int i = 0; i < path.size() - 1; i++) {
  79.         int weight = mp[{path[i], path[i+1]}];
  80.         res = max(res, weight);
  81.     }
  82.     return d[n] - res + res / 2;
  83. }
  84.  
  85. signed main() {
  86.     nhap();
  87.     cout << min(dijkstra(1), bfs(1));
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 8048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-9223372036854775808
https://ideone.com/xcxnVP
language:
C++14 (clang 8.0)
created:
31 days ago
visibility:
secret

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!