fork download 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. const int INF = 987654321;
  7. vector<pair<int, int>> trees[1001];
  8. int N, M;
  9.  
  10. int calcDist(int start, int dest){
  11. 	int dist[1001];
  12. 	for(int i=1;i<=N;i++) dist[i] = INF;
  13. 	priority_queue<pair<int, int>> pq;
  14. 	pq.push(make_pair(0, start));
  15. 	dist[start] = 0;
  16.  
  17. 	while(!pq.empty()){
  18. 		int currentDist = -pq.top().first;
  19. 		int current = pq.top().second;
  20. 		cout<<current<<" ";
  21. 		pq.pop();
  22.  
  23. 		for(int i=0;i<trees[current].size();i++){
  24. 			int nextDist = trees[current][i].first + currentDist;
  25. 			int next = trees[current][i].second;
  26.  
  27. 			if(dist[next] > nextDist){
  28. 				dist[next] = nextDist;
  29. 				pq.push(make_pair(-nextDist, next));
  30. 			}
  31. 		}
  32. 	}
  33.  
  34. 	return dist[dest];
  35. }
  36.  
  37. int main() {
  38.  
  39. 	cin>>N>>M;
  40.  
  41. 	for(int i=1;i<=N-1;i++){
  42. 		int node1, node2, cost;
  43. 		cin>>node1>>node2>>cost;
  44.  
  45. 		trees[node1].push_back(make_pair(cost, node2));
  46. 		trees[node2].push_back(make_pair(cost, node1));
  47. 	}
  48. 	for(int i=0;i<M;i++){
  49. 		int from, to;
  50. 		cin>>from>>to;
  51.  
  52. 		cout<<calcDist(from, to)<<'\n';
  53. 	}
  54.  
  55. 	return 0;
  56. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
4 1
2 1 2
4 3 2
1 4 3
3 2
stdout 
3 4 1 2 7
https://ideone.com/SWpMzF
language:
C++ (gcc 8.3)
created:
16 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!