fork download
copy 
  1. #include <climits>
  2. #include <iostream>
  3. #include <set>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. struct edge { int to, length; };
  8.  
  9. int dijkstra(const vector< vector<edge> > &graph, int source, int target) {
  10.     vector<int> min_distance( graph.size(), INT_MAX );
  11.     min_distance[ source ] = 0;
  12.     set< pair<int,int> > active_vertices;
  13.     active_vertices.insert( {0,source} );
  14.     while (!active_vertices.empty()) {
  15. 	    int where = active_vertices.begin()->second;
  16.     	if (where == target) return min_distance[where];
  17.     	active_vertices.erase( active_vertices.begin() );
  18.     	for (const auto &ed : graph[where])
  19.     		if (min_distance[ed.to] > min_distance[where] + ed.length) {
  20.     			active_vertices.erase( { min_distance[ed.to], ed.to } );
  21.     			min_distance[ed.to] = min_distance[where] + ed.length;
  22.     			active_vertices.insert( { min_distance[ed.to], ed.to } );
  23.     		}
  24.     	}
  25.     return INT_MAX;
  26. }
  27.  
  28. int main() {
  29. 	vector< vector<edge> > graph = { { {1,1}, {3,2} }, { {2,1} }, { {3,1} }, { } };
  30. 	cout << dijkstra(graph,0,3) << endl;
  31. 	cout << dijkstra(graph,0,2) << endl;
  32. 	cout << dijkstra(graph,1,2) << endl;
  33. 	cout << dijkstra(graph,2,0) << endl;
  34. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
2
1
2147483647
https://ideone.com/mhfmVH
language:
C++14 (gcc 8.3)
created:
8 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!