fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector <pair<int,int>> adj_list[1000];
  4. priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> pq;
  5. int cost[1000];
  6. int parent[1000];
  7.  
  8. void dijkstra(int s){
  9.     for(int i=0;i<1000;i++){
  10.         cost[i]=INT_MAX;
  11.     }
  12.     cost[s]=0;
  13.     parent[s]=s;
  14.     pq.push({cost[s],s});
  15.  
  16.     while(!pq.empty()){
  17.         int u=pq.top().second;
  18.         pq.pop();
  19.  
  20.         for(int i=0;i<adj_list[u].size();i++){
  21.             int v=adj_list[u][i].first;
  22.             int weight=adj_list[u][i].second;
  23.  
  24.             if(cost[u]+ weight<cost[v]){
  25.                 cost[v]=cost[u]+weight;
  26.                 parent[v]=u;
  27.                 pq.push({cost[v],v});
  28.             }
  29.         }
  30.  
  31.     }
  32. }
  33.  
  34. int main(){
  35.     int nodes,edges;cin>>nodes>>edges;
  36.     int u,v,w;
  37.     for(int i=1;i<=edges;i++){
  38.         cin>>u>>v>>w;
  39.         adj_list[u].push_back({v,w});
  40.     }
  41.     int source,dest;
  42.     cin>>source>>dest;
  43.     dijkstra(source);
  44.     cout<<cost[dest]<<"\n";
  45.  
  46.     cout<<"traceback: ";
  47.     int x=dest;
  48.     vector<int> traceback;
  49.     traceback.push_back(x);
  50.     while(parent[x]!=x){
  51.         traceback.push_back(parent[x]);
  52.         x=parent[x];
  53.     }
  54.     reverse(traceback.begin(),traceback.end());
  55.     for(auto x: traceback) cout<<x<<" ";
  56. /*
  57. input
  58. 6 8
  59.  
  60. 1 2 7
  61. 1 3 12
  62. 2 3 2
  63. 2 4 9
  64. 3 5 10
  65. 4 6 1
  66. 5 4 4
  67. 5 6 5
  68.  
  69. 1 6
  70. */
  71. }
  72.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 8
 
1 2 7
1 3 12
2 3 2
2 4 9
3 5 10
4 6 1
5 4 4
5 6 5
 
1 6
stdout
copy 
17
traceback: 1 2 4 6
https://ideone.com/3LyMZw
language:
C++ (gcc 8.3)
created:
7 hours 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!