SHARE
TWEET

Untitled

a guest Feb 17th, 2018 1,409 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4.  
  5. using namespace std;
  6.  
  7. typedef long long li;
  8.  
  9. const int N = 200 * 1000 + 13;
  10. const li INF64 = 1e18;
  11.  
  12. int n, m;
  13. li a[N];
  14. vector<pair<int, li>> g[N];
  15.  
  16. li dist[N];
  17.  
  18. void Dijkstra(){
  19.     set<pair<li, int>> q;
  20.     forn(i, n){
  21.         dist[i] = a[i];
  22.         q.insert({dist[i], i});
  23.     }
  24.    
  25.     while (!q.empty()){
  26.         int v = q.begin()->second;
  27.         q.erase(q.begin());
  28.        
  29.         for (auto it : g[v]){
  30.             int u = it.first;
  31.             li w = it.second;
  32.            
  33.             if (dist[u] > dist[v] + w){
  34.                 q.erase({dist[u], u});
  35.                 dist[u] = dist[v] + w;
  36.                 q.insert({dist[u], u});
  37.             }
  38.         }
  39.     }
  40. }
  41.  
  42. int main() {
  43.     scanf("%d%d", &n, &m);
  44.     forn(_, m){
  45.         int f, t;
  46.         li w;
  47.         scanf("%d%d%lld", &f, &t, &w);
  48.         --f, --t;
  49.         w *= 2;
  50.         g[f].push_back({t, w});
  51.         g[t].push_back({f, w});
  52.     }
  53.     forn(i, n){
  54.         scanf("%lld", &a[i]);
  55.     }
  56.    
  57.     Dijkstra();
  58.     forn(i, n)
  59.         printf("%lld ", dist[i]);
  60.     puts("");
  61.     return 0;
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top