fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define MOD 1000000007
  5. #define PI 4 * atan(1)
  6. typedef long long ll;
  7. typedef vector<int> vi;
  8. typedef pair<int, int> pii;
  9. typedef vector<long long> vll;
  10. typedef long int int32;
  11. typedef unsigned long int uint32;
  12. typedef long long int int64;
  13. typedef unsigned long long int uint64;
  14.  
  15. int n,e,u;
  16. vector<pii> adj[1004];
  17.  
  18.  
  19. inline void solve(int test){
  20.     cin >> n >> e >> u;
  21.     int x,y,w; 
  22.     for(int i=1; i<=n; i++) adj[i].clear();
  23.     for(int i=0; i<e; i++){
  24.         cin >> x >> y >> w;
  25.         adj[x].push_back({y,w});
  26.         adj[y].push_back({x, w});
  27.     }
  28.     int dist[n+1] = {0};
  29.     for(int i=1; i<=n; i++) dist[i] = INT_MAX;
  30.     dist[u] = 0;
  31.     priority_queue<pii> pq;
  32.     pq.push({0, u});
  33.     while(!pq.empty()){
  34.         pii f = pq.top(); pq.pop();
  35.         int node = f.second, d = f.first;
  36.         for(pii p: adj[node]){
  37.             int v =  p.first;
  38.             int weight = p.second;
  39.             if(dist[v] > dist[node] + weight){
  40.                 dist[v] = dist[node] + weight;
  41.                 pq.push({dist[v], v});
  42.             }
  43.         }
  44.     }
  45.     for(int i=1; i<=n; i++) cout << dist[i] << " ";
  46.     cout << "\n";
  47.  
  48. }   
  49.  
  50. int main(){
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(NULL);
  53.     cout.tie(NULL);
  54.     int typetest = 1;
  55.     if (typetest){
  56.         int t;
  57.         cin >> t;
  58.         for(int i=1; i<=t; i++){
  59.             solve(i);
  60.         }
  61.     }
  62.     else solve(0);
  63. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gjxdCs
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!