fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void algo(int s, vector<vector<pair<int, int> > > adj, vector<bool> &visited, vector<int> &dist, int n){
  5.   visited[s] = true;
  6.   dist[s] = 0;
  7.   queue<int> q;
  8.   q.push(s);
  9.   while(!q.empty()){
  10.     //cout << "inside" << endl;
  11.     int temp = q.front();
  12.     q.pop();
  13.     vector<pair<int, int> >::iterator i;
  14.     int u = -1, min_dist = INT_MAX;
  15.     for(i = adj[temp].begin(); i != adj[temp].end(); i++){
  16.       if(dist[(i->first)] > dist[temp] + i->second){
  17.         dist[(i->first)] = dist[temp] + i->second;
  18.       }
  19.       // if(!visited[(i->first)] && dist[(i->first)] < min_dist){
  20.       //   min_dist = dist[(i->first)];
  21.       //   u = (i->first);
  22.       //   q.push(u);
  23.       //   visited[u] = true;
  24.       // }
  25.       for(int j = 1; j <= n; j++){
  26.         if(!visited[j] && dist[j] < min_dist){
  27.           min_dist = dist[j];
  28.           u = j;
  29.         }
  30.       }
  31.       if(u != -1){
  32.         q.push(u);
  33.         visited[u] = true;
  34.       }
  35.     }
  36.   }
  37. }
  38.  
  39. int main(){
  40.   int t;
  41.   cin >> t;
  42.   while(t--){
  43.     int n, m, u, v, w, s;
  44.     cin >> n >> m;
  45.     vector<vector<pair<int, int> > > adj(n+1, vector<pair<int, int> >());
  46.     for(int i = 0; i < m; i++){
  47.       cin >> u >> v >> w;
  48.       adj[u].push_back(make_pair(v, w));
  49.       adj[v].push_back(make_pair(u, w));
  50.     }
  51.     cin >> s;
  52.     vector<int> dist(n+1, INT_MAX);
  53.     vector<bool> visited(n+1, false);
  54.     algo(s, adj, visited, dist, n);
  55.     for(int i = 1; i <= n; i++){
  56.       if(i != s && dist[i] != INT_MAX){
  57.         cout << dist[i] << " ";
  58.       }
  59.       else if(i != s && dist[i] == INT_MAX){
  60.         cout << -1 << " ";
  61.       }
  62.     }
  63.     cout << endl;
  64.   }
  65. }
  66.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
1 4 4 1 2 24 1 4 20 3 1 3 4 3 12 1
stdout 
24 3 15
https://ideone.com/VdXkFp
language:
C++14 (gcc 8.3)
created:
5 years 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!