fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. class Graph{
  6.     unordered_map<int, list<pair<int,int> > > m;
  7.  
  8. public:
  9.  
  10.     void addEdge(int u,int v,int dist,bool bidir=true){
  11.         m[u].push_back(make_pair(v,dist)); 
  12.         if(bidir){
  13.             m[v].push_back(make_pair(u,dist));
  14.         }
  15.  
  16.     }
  17.     void printAdj(){
  18.         //Let try to print the adj list
  19.         //Iterate over all the key value pairs in the map 
  20.         for(auto j:m){
  21.  
  22.             cout<<j.first<<"->";
  23.  
  24.             //Iterater over the list of cities
  25.             for(auto l: j.second){
  26.                     cout<<"("<<l.first<<","<<l.second<<")";
  27.  
  28.             }
  29.             cout<<endl;
  30.         }
  31.  
  32.     }
  33.  
  34. 	void dijkastraSSSP(int V ,int src){
  35.  
  36. 		unordered_map<int,int> dist;
  37.  
  38.         //Set all distance to infinity
  39.         for(auto j:m){
  40.             dist[j.first] = INT_MAX;
  41.         }
  42. 		//pair is of dist anf node
  43. 		set<pair<int , int> > s;
  44.  
  45. 		s.insert(make_pair(0 , src));
  46.  
  47. 		while(!s.empty()){
  48.  
  49. 			pair<int, int> tmp = *(s.begin());
  50. 			//removing this pair  
  51.         	s.erase(s.begin()); 
  52. 			int node = tmp.second;
  53. 			int dist_curr = tmp.first;
  54.  
  55. 			//now going through the neighbours of this node
  56. 			for(auto neighbours :m[node]){
  57.  
  58. 				if(dist_curr + neighbours.second <dist[neighbours.first] ){
  59.  
  60. 					int dest = neighbours.first;
  61. 					auto f = s.find( make_pair(dist[dest],dest));
  62.                     if(f!=s.end()){
  63.                         s.erase(f);
  64.                     }
  65.  
  66.                     //Insert the new pair
  67.                     dist[dest] = dist_curr + neighbours.second;
  68.                     s.insert(make_pair(dist[dest],dest));
  69.  
  70.                 }
  71.  
  72.             }
  73.         }
  74.         //Lets print distance to all other node from src
  75.         for(auto d:dist){
  76.  
  77.             cout<<d.second<<" ";
  78.         }
  79. 	}
  80. };
  81.  
  82.  
  83. int main(){
  84.  
  85.  
  86.     int t=0;
  87. 	cin>>t;
  88. 	while(t--){
  89.     Graph g;
  90. 	int n , m;
  91. 	cin>>n>>m;
  92.  
  93. 	for(int i =0;i<m;i++){
  94.     	int x=0 , y=0 , dist=0;
  95. 		cin>>x>>y>>dist;
  96. 		g.addEdge(x , y , dist);
  97. 	}
  98. 	int s;
  99. 	cin>>s;
  100.     //g.printAdj();
  101.    	g.dijkastraSSSP(s , n);
  102. 	}
  103. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/H6dUQb
language:
C++ (gcc 8.3)
created:
6 years 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!