fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4.  
  5. int32_t main() {
  6.   ios::sync_with_stdio(false);cin.tie(nullptr);
  7.   int n, m;
  8.   cin >> n >> m;
  9.   vector<vector<pair<int, int>>>routes(n+1);
  10.   for(int i = 0; i < m; i++) {
  11.     int a, b, c;
  12.     cin >> a >> b >> c;
  13.     routes[a].push_back({c, b});
  14.   }
  15.   set<pair<int, int>>queu;
  16.   vector<bool>visited(n+1, 0);
  17.   vector<int>dist(n+1, 1e18);
  18.   queu.insert({0, 1});
  19.   while(!queu.empty()) {
  20.     int root = (*queu.begin()).second;
  21.     int curdist = (*queu.begin()).first;
  22.     queu.erase(queu.begin());
  23.     if(visited[root]) continue;
  24.     visited[root] = true;
  25.     dist[root] = min(dist[root], curdist);
  26.     for(int i = 0; i < routes[root].size(); i++) {
  27.       if(visited[routes[root][i].second]) continue;
  28.       queu.insert({curdist+routes[root][i].first, routes[root][i].second});
  29.     }
  30.   }
  31.   for(int i = 1; i <= n; i++) {
  32.     cout << dist[i] << " ";
  33.   }
  34.   return 0;
  35. }
Success #stdin #stdout 0s 5292KB
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/JZZU1a
language:
C++14 (gcc 8.3)
created:
1 day 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!