fork(16) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, e; //nodes, edges
  4. vector<vector<pair<int, int> > > adj; //first is adjecent node, second is edge cost
  5. struct node {
  6. 	int x, cst;
  7. 	node(int x, int cst) :
  8. 			x(x), cst(cst) {
  9. 	}
  10. 	bool operator<(const node &a) const {
  11. 		return a.cst < cst;
  12. 	}
  13. };
  14. int dijk(int src, int des) {
  15. 	vector<int> cost(n + 1, 1e9);
  16. 	priority_queue<node> que;
  17. 	que.push(node(src, 0));
  18. 	cost[src] = 0;
  19. 	while (que.size()) {
  20. 		int x = que.top().x, cst = que.top().cst;
  21. 		que.pop();
  22. 		if (x == des) {
  23. 			return cst;
  24. 		}
  25. 		for (int i = 0, ln = adj[x].size(); i < ln; ++i) {
  26. 			int y = adj[x][i].first, _cst = adj[x][i].second;
  27. 			if (cst + _cst < cost[y]) {
  28. 				cost[y] = cst + _cst;
  29. 				que.push(node(y, cost[y]));
  30. 			}
  31. 		}
  32. 	}
  33. }
  34. int main() {
  35. #ifndef ONLINE_JUDGE
  36. 	freopen("a.in", "r", stdin);
  37. #endif
  38. 	int q;
  39. 	cin >> n >> e >> q; // qeuery
  40. 	adj.clear();
  41. 	adj.resize(n + 1);
  42. 	while (e--) {
  43. 		int x, y, z; //pair of nodes, cost
  44. 		cin >> x >> y >> z;
  45. 		adj[x].push_back(make_pair(y, z));
  46. 	}
  47. 	while (q--) {
  48. 		int src, des;
  49. 		cin >> src >> des;
  50. 		cout << dijk(src, des) << endl;
  51. 	}
  52. 	return 0;
  53. }
  54.  
Runtime error #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xEBzsj
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!