fork download 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. #define all(s) s.begin(), s.end()
  6. using namespace std;
  7. const int N = 1e5 + 5;
  8. const ll inf = 1e18;
  9. typedef pair<ll, ll> ii;
  10. ll d[N];
  11. ll n, m, k;
  12. vector<ii> a[N];
  13. void dijkstra()
  14. {
  15.     priority_queue<ii, vector<ii>, greater<ii> > q;
  16.     for(int i = 1; i <= n; i++)
  17.         if(!d[i])
  18.             q.push({0, i});
  19.     while(q.size())
  20.     {
  21.         ii top = q.top();
  22.         q.pop();
  23.         ll dis = top.fi;
  24.         int u = top.se;
  25.         if(dis > d[u]) continue;
  26.         for(auto p : a[u])
  27.         {
  28.             int v = p.fi;
  29.             ll w = p.se;
  30.             if(d[v] > d[u] + w)
  31.             {
  32.                 d[v] = d[u] + w;
  33.                 q.push({d[v], v});
  34.             }
  35.         }
  36.     }
  37. }
  38. int main()
  39. {
  40.     cin >> n >> k;
  41.     for(int i = 1; i <= n; i++)
  42.         d[i] = inf;
  43.     for(int i = 1; i <= k; i++)
  44.     {
  45.         int x;
  46.         cin >> x;
  47.         d[x] = 0;
  48.     }
  49.     cin >> m;
  50.     for(int i = 1; i <= m; i++)
  51.     {
  52.         ll u, v, w;
  53.         cin >> u >> v >> w;
  54.         a[u].push_back({v, w});
  55.         a[v].push_back({u, w});
  56.     }
  57.     dijkstra();
  58.     for(int i = 1; i <= n; i++)
  59.         cout << d[i] << ' ';
  60. }
  61.  
Success #stdin #stdout 0.01s 6036KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/rvXN41
language:
C++ (gcc 8.3)
created:
5 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!