fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5.  
  6.   void shortestpath(vector<pair<ll,ll> > adj[], ll V, ll src)
  7. {
  8.     priority_queue< pair<ll,ll>, vector <pair<ll,ll>> , greater<pair<ll,ll>> > pq;
  9.     vector<ll> dist(V, 1e17);
  10. vector<ll> vis(V+1,0);
  11.     pq.push(make_pair(0, src));
  12.     dist[src] = 0;
  13. vis[src]=1;
  14.     while (!pq.empty())
  15.     {
  16.         ll u = pq.top().second;
  17.         pq.pop();
  18. vis[u]=1;
  19.         for (auto x : adj[u])
  20.         {
  21.             ll v = x.first;
  22.             ll weight = x.second;
  23.  
  24.             if (!vis[v]&&dist[v] > dist[u] + weight)
  25.             {
  26.                 dist[v] = dist[u] + weight;
  27.                 pq.push(make_pair(dist[v], v));
  28.             }
  29.         }
  30.     }
  31. // return dist;
  32.  for(int i=1;i<V;i++)cout<<dist[i]<<" ";
  33. }
  34.  
  35.  
  36. int main()
  37. {
  38.  
  39.  long long int n,m;
  40.  cin>>n>>m;
  41. vector<pair<ll,ll>>ad[n+1];
  42. for(int i=0;i<m;i++)
  43. {
  44.     long long int a,b,w;
  45.     cin>>a>>b>>w;
  46.     ad[a].push_back({b,w});
  47. }
  48.  shortestpath(ad,n+1,1);
  49.  
  50.  
  51. }
  52.  
Success #stdin #stdout 0s 4140KB
comments (?)
stdin
copy 
3 4
1 2 6
1 3 2
3 2 3
1 3 4
stdout
copy 
0 5 2
https://ideone.com/SEcRXD
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!