fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<ll, int> pli;
  6.  
  7. const ll INF = 1e18;
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.  
  13.     int n, m;
  14.     cin >> n >> m;
  15.  
  16.     vector<ll> a(n + 1);
  17.     for (int i = 1; i <= n; i++) {
  18.         cin >> a[i];
  19.     }
  20.  
  21.     vector<vector<pair<int, ll>>> adj(n + 1);
  22.     for (int i = 0; i < m; i++) {
  23.         int u, v;
  24.         ll w;
  25.         cin >> u >> v >> w;
  26.         adj[u].emplace_back(v, w);
  27.         adj[v].emplace_back(u, w);
  28.     }
  29.  
  30.     vector<vector<ll>> dist(n + 1, vector<ll>(3, INF));
  31.  
  32.  
  33.     priority_queue<pair<ll, pair<int, int>>, 
  34.                    vector<pair<ll, pair<int, int>>>,
  35.                    greater<pair<ll, pair<int, int>>>> pq;
  36.  
  37.     dist[1][0] = 0;
  38.     pq.push({0, {1, 0}});
  39.  
  40.     while (!pq.empty()) {
  41.         auto [cost, info] = pq.top();
  42.         pq.pop();
  43.         int u = info.first;
  44.         int state = info.second;
  45.  
  46.         if (cost != dist[u][state]) continue;
  47.  
  48.         for (auto [v, w] : adj[u]) {
  49.             if (dist[v][state] > cost + w) {
  50.                 dist[v][state] = cost + w;
  51.                 pq.push({dist[v][state], {v, state}});
  52.             }
  53.         }
  54.  
  55.         if (state == 0) {
  56.  
  57.             if (dist[u][1] > cost + a[u]) {
  58.                 dist[u][1] = cost + a[u];
  59.                 pq.push({dist[u][1], {u, 1}});
  60.             }
  61.         } 
  62.         else if (state == 1) {
  63.  
  64.             if (dist[u][2] > cost - a[u]) {
  65.                 dist[u][2] = cost - a[u];
  66.                 pq.push({dist[u][2], {u, 2}});
  67.             }
  68.         }
  69.  
  70.     }
  71.  
  72.  
  73.     ll ans = min({dist[n][0], dist[n][1], dist[n][2]});
  74.     cout << ans << "\n";
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
4 4
4 1 6 5
1 2 3
1 3 1
2 4 3
3 4 3
stdout 
2
https://ideone.com/WCYbSm
language:
C++14 (gcc 8.3)
created:
5 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!