fork download
copy 
  1. #include <bits/stdc++.h>
  2.  using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<ll, ll> ii;
  6. #define fi first
  7. #define se second
  8.  
  9. struct ele
  10. {
  11.     ll u, w, k;
  12.     bool operator > (const ele &other) const
  13.     {
  14.         return w > other.w;
  15.     }
  16. };
  17.  
  18. const ll inf = 1e18;
  19. const int mx = 1e5 + 7;
  20. int n, m, c[mx];
  21. vector<ii> adj[mx];
  22. ll nd[mx], d[mx][2];
  23.  
  24. void init()
  25. {
  26.     for (int i = 1; i <= n; i++) {
  27.         nd[i] = d[i][0] = d[i][1] = inf;
  28.     }
  29. }
  30.  
  31. void dijkstra2()
  32. {
  33.     nd[n] = 0;
  34.     priority_queue<ii, vector<ii>, greater<ii>> q;
  35.     q.push({0, n});
  36.     while(!q.empty()) {
  37.         auto [kc, u] = q.top(); q.pop();
  38.         if (kc > nd[u]) continue;
  39.         for (auto [v, w] : adj[u]) {
  40.             if (nd[u] + w < nd[v]) {
  41.                 nd[v] = nd[u] + w;
  42.                 q.push({nd[v], v});
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. void dijkstra1()
  49. {
  50.     d[1][0] = 0;
  51.     d[1][1] = nd[1];
  52.     priority_queue<ele, vector<ele>, greater<ele>> q;
  53.     q.push({1, 0, 0});
  54.     q.push({1, nd[1], 1});
  55.     while(!q.empty()) {
  56.         auto [u, kc, k] = q.top(); q.pop();
  57.         if (kc > d[u][k]) continue;
  58.         for (auto [v, w] : adj[u]) {
  59.             if (d[u][k] + w < d[v][k]) {
  60.                 d[v][k] = d[u][k] + w;
  61.                 q.push({v, d[v][k], k});
  62.             }
  63.             if (k == 0 && d[u][k] + w + nd[v] < d[v][1]) {
  64.                 d[v][1] = d[u][k] + w + nd[v];
  65.                 q.push({v, d[v][1], 1});
  66.             }
  67.         }
  68.     }
  69. }
  70.  
  71. int main()
  72. {
  73.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  74.  
  75.     cin >> n >> m;
  76.     for (int i = 1; i <= n; i++) {
  77.         cin >> c[i];
  78.     }
  79.     for (int i = 1; i <= m; i++) {
  80.         int u, v, w;
  81.         cin >> u >> v >> w;
  82.         adj[u].push_back({v, w});
  83.         adj[v].push_back({u, w});
  84.     }
  85.     init();
  86.     dijkstra2();
  87.     dijkstra1();
  88.     ll ans = inf;
  89.     for (int i = 1; i <= n; i++) {
  90.         ans = min({ans, d[i][1] + c[i], d[i][0] + c[i] + nd[i]});
  91.     }
  92.     cout << ans;
  93. }
Success #stdin #stdout 0.01s 7732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/sYppSE
language:
C++ (gcc 8.3)
created:
11 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!