fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pub push_back
  3. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  4. #define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
  5. #define all(x) begin(x), end(x)
  6. #define pii pair<int, int>
  7. #define fi first
  8. #define se second
  9. #define int long long
  10. using namespace std;
  11.  
  12. const int N = 1e5 + 5;
  13. const int M = 350;
  14. const int LOG = 19;
  15. const int inf = 3e18;
  16.  
  17. struct node {int fi, se;};
  18. struct cmp {
  19.     bool operator()(node &a, node &b) {
  20.         return a.se > b.se;
  21.     }
  22. };
  23.  
  24. int n, m, c[N], d1[N], dn[N], D[N];
  25. vector <pii> a[N];
  26.  
  27. void ditcha(int tu, int o) {
  28.     if (o == 1) memset(d1, 0x3f, sizeof(d1));
  29.     if (o == 2) memset(dn, 0x3f, sizeof(dn));
  30.  
  31.     priority_queue <node, vector<node>, cmp> pq;
  32.     pq.push({tu, 0});
  33.  
  34.     if (o == 1) d1[tu] = 0;
  35.     if (o == 2) dn[tu] = 0;
  36.  
  37.     while(!pq.empty()) {
  38.         node tt = pq.top(); pq.pop();
  39.         int u = tt.fi;
  40.         int du = tt.se;
  41.  
  42.         if (o == 1 && du > d1[u]) continue;
  43.         if (o == 2 && du > dn[u]) continue;
  44.  
  45.         for(pii x : a[u]) {
  46.             int v = x.fi;
  47.             int w = x.se;
  48.  
  49.             if (o == 1 && d1[v] > d1[u] + w) {
  50.                 d1[v] = d1[u] + w;
  51.                 pq.push({v, d1[v]});
  52.             }
  53.             if (o == 2 && dn[v] > dn[u] + w) {
  54.                 dn[v] = dn[u] + w;
  55.                 pq.push({v, dn[v]});
  56.             }
  57.         }
  58.     }
  59. }
  60. void ditchaDaLuong() {
  61.      memset(D, 0x3f, sizeof(D));
  62.      priority_queue <node, vector<node>, cmp> pq;
  63.      FOR(u, 1, n, 1) {
  64.         pq.push({u, c[u]});
  65.         D[u] = c[u];
  66.      }
  67.  
  68.     while(!pq.empty()) {
  69.         node tt = pq.top(); pq.pop();
  70.         int u = tt.fi;
  71.         int du = tt.se;
  72.  
  73.         for(pii x : a[u]) {
  74.             int v = x.fi;
  75.             int w = x.se;
  76.  
  77.             if (D[v] > D[u] + w) {
  78.                 D[v] = D[u] + w;
  79.                 pq.push({v, D[v]});
  80.             }
  81.         }
  82.     }
  83. }
  84. void solve() {
  85.     cin >> n >> m;
  86.     FOR(i, 1, n, 1) cin >> c[i];
  87.     FOR(i, 1, m, 1) {
  88.         int u, v, w; cin >> u >> v >> w;
  89.         a[u].pub({v, w});
  90.         a[v].pub({u, w});
  91.     }
  92.  
  93.     ditcha(1, 1);
  94.     ditcha(n, 2);
  95.     ditchaDaLuong();
  96.  
  97.     int ans = inf;
  98.  
  99.     FOR(v, 1, n, 1) {
  100.         int cost = (d1[v] + D[v] + dn[v]);
  101.         ans = min(ans, cost);
  102.     }
  103.  
  104.     cout << ans << '\n';
  105.  
  106. }
  107.  
  108. signed main() {
  109.     #define name "baitap"
  110.     if (ifstream(name".inp")) {
  111.         freopen(name".inp", "r", stdin);
  112.         freopen(name".out", "w", stdout);
  113.     }
  114.  
  115.     ios_base::sync_with_stdio(0);
  116.     cin.tie(0);
  117.     cout.tie(0);
  118.  
  119.     solve();
  120. }
  121.  
Success #stdin #stdout 0.01s 8164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3000000000000000000
https://ideone.com/CtYDTf
language:
C++ (gcc 8.3)
created:
3 days 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!