Guest User

Untitled

a guest
Feb 17th, 2018
3,461
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