fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pr pair<int,int>
  7.  
  8. const ll MAXN = 100005;
  9. const ll INF = 1e18;
  10. vector <pair<int,int>> A[MAXN];
  11. vector <bool> ktra(MAXN,false);
  12. vector <ll> vet(MAXN,0),v;
  13. priority_queue<pr,vector<pr>,greater<pr>> Q;
  14. void dijkstra(int n,int xp, int dich){
  15.     vector <ll> L(n+1,INF);
  16.     L[xp]=0;
  17.     Q.push({0,xp});
  18.     while(!Q.empty()){
  19.         auto canh=Q.top();
  20.         ll u=canh.se;
  21.         Q.pop();
  22.         if(ktra[u]) continue;
  23.         ktra[u]=true;
  24.         for(auto x:A[u]){
  25.             ll v=x.fi,w=x.se;
  26.             if(L[v]>L[u]+w){
  27.                 L[v]=L[u]+w;
  28.                 vet[v]=u;
  29.                 Q.push({L[v],v});
  30.             }
  31.         }
  32.     }
  33.  
  34.     ll ans=L[dich];
  35.     if(L[dich]==INF){
  36.         cout << 0 << "\n";
  37.     }
  38.     else{
  39.         v.push_back(dich);
  40.         while(dich!=xp){
  41.             v.push_back(vet[dich]);
  42.             dich=vet[dich];
  43.         }
  44.         cout << ans << "\n";
  45.         for(ll i=v.size()-1 ; i>=0 ; i--) cout << v[i] << " ";
  46.     }
  47. }
  48.  
  49.  
  50. int main(){
  51.     ll n,m; cin >> n >> m;
  52.     for(ll i=1 ; i<=m ; i++){
  53.         ll u,v,x; cin >> u >> v >> x;
  54.         A[u].push_back({v,x});
  55.         A[v].push_back({u,x});
  56.     }
  57.     ll xp,dich;
  58.     cin >> xp >> dich;
  59.     dijkstra(n,xp,dich);
  60. }
  61.  
Runtime error #stdin #stdout 0.02s 6548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Sj7WKx
language:
C++ (gcc 8.3)
created:
157 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!