fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector < pair<int,int> > adj_list[100];
  5. int dist[100];
  6. int par[100];
  7.  
  8. int Dijkstra(int start, int dest)
  9. {
  10.     dist[start] = 0;
  11.     par[start] = -1;
  12.     priority_queue < pair <int,int> , vector < pair <int,int> >, greater < pair <int,int> > > pq;
  13.     pq.push({dist[start],start});
  14.     while(!pq.empty())
  15.     {
  16.         pair <int,int> tp = pq.top();
  17.         pq.pop();
  18.         int u = tp.second;
  19.         int cost = tp.first;
  20.         if(u == dest)
  21.         {
  22.             return cost;
  23.         }
  24.         for(int i=0;i<adj_list[u].size();i++)
  25.         {
  26.             pair <int,int> child_pair = adj_list[u][i];
  27.             int v = child_pair.second;
  28.             int wt = child_pair.first;
  29.             if(dist[u]+wt < dist[v])
  30.             {
  31.                 dist[v] = dist[u] + wt;
  32.                 par[v] = u;
  33.                 pq.push({dist[v],v});
  34.             }
  35.         }
  36.     }
  37.     return -1;
  38. }
  39.  
  40. int main()
  41. {
  42.     int nodes, edges;
  43.     cin>>nodes>>edges;
  44.     for(int i=1;i<=edges;i++)
  45.     {
  46.         int u,v,wt;
  47.         cin>>u>>v>>wt;
  48.         adj_list[u].push_back({wt,v});
  49.     }
  50.     int start, dest;
  51.     cin>>start>>dest;
  52.     for(int i=1;i<=nodes;i++)
  53.     {
  54.         dist[i] = 1000000000;
  55.     }
  56.     int cost = Dijkstra(start,dest);
  57.     if(cost == -1)
  58.     {
  59.         cout<<"Disconnected"<<endl;
  60.     }
  61.     else
  62.     {
  63.         cout<<"Connected. Min Cost: "<<cost<<endl;
  64.         int currNode = dest;
  65.         stack <int> st;
  66.         while(currNode != -1)
  67.         {
  68.             st.push(currNode);
  69.             currNode = par[currNode];
  70.         }
  71.         cout<<"Path: ";
  72.         while(!st.empty())
  73.         {
  74.             cout<<st.top()<<" ";
  75.             st.pop();
  76.         }
  77.     }
  78. }
  79.  
  80.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
10 15
1 2 10 
2 4 10
1 5 15
2 3 4
1 3 5
4 5 15
4 7 15
6 5 5
5 7 30
7 8 10
8 6 10
8 9 5
7 10 20
9 10 4
4 6 5
stdout
copy 
Connected. Min Cost: 5
Path: 6 5
https://ideone.com/BLFeC8
language:
C++ (gcc 8.3)
created:
3 days 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!