fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<long long, long long> pll;
  5.  
  6. int main() {
  7.     int n, m; 
  8.     // n = cities, m = flights
  9.     cin >> n >> m;
  10.  
  11.     vector<pll> adj[n+1];
  12.  
  13.     for (int i=0; i<m; i++) {
  14.         long long a, b, c;
  15.         // flight from a to b with cost c
  16.         cin >> a >> b >> c;
  17.         adj[a].push_back( {b, c} );
  18.     }
  19.  
  20.     vector<long long> dist(n+1, LLONG_MAX);
  21.  
  22.     // minimum priority queue
  23.     priority_queue< pll , vector<pll>, greater<pll> > pq; // smallest item first
  24.     // {dist, nodeNumber}
  25.     pq.push( {0, 1} ); 
  26.  
  27.     while(!pq.empty()) {
  28.         pll x = pq.top();
  29.         pq.pop();
  30.         long long d = x.first , cur = x.second;
  31.  
  32.         if (d >= dist[cur]) continue; // if (vis[cur]) continue
  33.         dist[cur] = d; // vis[cur] = true
  34.  
  35.         // for each adjacent node of cur
  36.         for (pll x: adj[cur]) {
  37.             long long v = x.first, c = x.second;
  38.             long long newDist = d + c;
  39.             if (newDist >= dist[v]) continue;
  40.             pq.push({newDist, v});
  41.         }
  42.     }
  43.  
  44.     for (int i=1; i<=n; i++) {
  45.         cout << dist[i] << " ";
  46.     }
  47.     cout << endl;
  48. }
Runtime error #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qqYjw6
language:
C++14 (gcc 8.3)
created:
1 year 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!