fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Edge {
  5.     int dest;
  6.     long long weight;
  7. };
  8.  
  9. int main() {
  10.     int n, m, s, t;
  11.     cin >> n >> m >> s >> t;
  12.     vector<vector<Edge>> g(n + 1);
  13.     g.reserve(n + 1);
  14.     while(m--){
  15.         int u, v;
  16.         long long c;
  17.         cin >> u >> v >> c;
  18.         g[u].push_back({v, c});
  19.         g[v].push_back({u, c});
  20.     }
  21.     const long long INF = 1e18;
  22.     priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  23.     vector<long long> dis(n + 1, INF);
  24.     vector<int> prev(n + 1, -1); 
  25.     pq.push({0, s});
  26.     dis[s] = 0;
  27.     while(!pq.empty()){
  28.         int u = pq.top().second;
  29.         long long d = pq.top().first;
  30.         pq.pop();
  31.         if(d > dis[u]) continue;
  32.         for(const auto& edge : g[u]){
  33.             int v = edge.dest;
  34.             long long w = edge.weight;
  35.             if(dis[v] > dis[u] + w){
  36.                 dis[v] = dis[u] + w;
  37.                 pq.push({dis[v], v});
  38.                 prev[v] = u;
  39.             }
  40.         }
  41.     }
  42.     if(dis[t] == INF){
  43.         cout << -1;
  44.         return 0;
  45.     }
  46.     vector<int> path;
  47.     for(int v = t; v != -1; v = prev[v]){
  48.         path.push_back(v);
  49.     }
  50.     reverse(path.begin(), path.end());
  51.     cout << dis[t] << '\n';
  52.     for(int node : path){
  53.         cout << node << ' ';
  54.     }
  55.     return 0;
  56. }
  57.  
Runtime error #stdin #stdout 1.29s 2095240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HDyFyQ
language:
C++ (gcc 8.3)
created:
194 days 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!