fork(1) download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const pair<int,vector<int>>& min(const pair<int,vector<int>>& a, const pair<int,vector<int>>& b) {
  8.   return (a.first < b.first) ? a : b;     // or: return !comp(b,a)?a:b; for version (2)
  9. }
  10.  
  11. pair<int,vector<int>> findShortestPath(vector<vector<int>>& graph, int v){
  12. 	vector<pair<int,vector<int>>> childs;
  13. 	for (int i=0; i<v; i++){
  14. 		if (graph[i][v] != -1){
  15. 			pair<int,vector<int>> path = findShortestPath(graph,i);
  16. 			path.second.push_back(v+1);
  17. 			childs.push_back(make_pair(path.first + graph[i][v], path.second));
  18. 		}
  19. 	}
  20. 	if (childs.size() == 2){
  21. 		pair<int,vector<int>> path = min(childs[0],childs[1]);
  22. 		return make_pair(path.first*2+1, path.second);
  23. 	}
  24. 	if (childs.size() == 1){
  25. 		return make_pair(childs[0].first,childs[0].second);
  26. 	}
  27. 	else{
  28. 		vector<int> start = {v+1};
  29. 		return make_pair(0,start);
  30. 	}
  31. }
  32.  
  33. int main()
  34. {
  35. 	int n, e;
  36. 	cin >> n; //num of vertices
  37. 	cin >> e; //num of queues
  38. 	vector<vector<int>> graph;
  39.  
  40. 	//initialize graph matrix cells to -1
  41. 	graph.resize(n);
  42. 	for (int i=0;i<n;i++){
  43. 		graph[i].resize(n);
  44. 		for (int j=0;j<n;j++)
  45. 			graph[i][j] = -1;
  46. 	}
  47.  
  48. 	//add edges and their weights
  49. 	for (int i=0;i<e;i++){
  50. 		int s,d,val;
  51. 		cin >> s >> d >> val;
  52. 		graph[s-1][d-1] = val;
  53. 	}
  54.  
  55. 	//run algorithm
  56. 	pair<int,vector<int>> path = findShortestPath(graph, n-1);
  57.  
  58. 	//print results
  59.     cout << path.first << endl;
  60.     for (int i=0;i<path.second.size()-1;i++)
  61.     	cout << path.second[i] << " -> ";
  62.     cout << path.second[path.second.size()-1] << endl;
  63.  
  64.     return 0;
  65. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
7
6
1 5 9
2 5 5
3 6 1
4 6 3
5 7 7
6 7 4
stdout
copy 
15
3 -> 6 -> 7
https://ideone.com/jAwH9k
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!