fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. bool minimize(T& a, const T& b) {
  13. 	if (b < a) {a = b; return true;}
  14. 	return false; 
  15. }
  16.  
  17. const int N = 1e5 + 5; 
  18.  
  19. int n, m;  
  20. vector<ii> adj[N]; 
  21.  
  22. struct Node {
  23. 	int u; ll d;  
  24. 	bool operator<(const Node& other) const {
  25. 		return d > other.d; 
  26. 	}
  27. }; 
  28.  
  29. ll dist[N]; // dist[u] = Đường đi ngắn nhất từ s đến u
  30.  
  31. void dijkstra(int s) {
  32. 	for (int u = 1; u <= n; u++) dist[u] = LINF; 
  33.  
  34. 	priority_queue<Node> pq;  
  35. 	dist[s] = 0;   
  36. 	pq.push({s, dist[s]});  
  37.  
  38. 	while (!pq.empty()) {
  39. 		Node front = pq.top(); pq.pop();  
  40. 		ll d = front.d; int u = front.u;  
  41.  
  42. 		if (d > dist[u]) continue;  
  43.  
  44. 		for (ii v : adj[u]) {
  45. 			if (minimize(dist[v.first], dist[u] + v.second)) {
  46. 				pq.push({v.first, dist[v.first]});
  47. 			}
  48. 		}
  49. 	}
  50. }
  51.  
  52. int main() {
  53. 	ios::sync_with_stdio(false); 
  54. 	cin.tie(nullptr); 	
  55. 	cin >> n >> m; 
  56.  
  57. 	for (int i = 0; i < m; i++) {
  58. 		int u, v, w; 
  59. 		cin >> u >> v >> w; 
  60. 		adj[u].push_back({v, w}); 
  61. 	}
  62.  
  63. 	dijkstra(1); 
  64.  
  65. 	for (int u = 1; u <= n; u++) {
  66. 		cout << dist[u] << ' ' ; 
  67. 	}
  68. }
Success #stdin #stdout 0.01s 5936KB
comments (?)
stdin
copy 
3 4
1 2 6
1 3 2
3 2 3
1 3 4
stdout
copy 
0 5 2
https://ideone.com/MIyJd6
language:
C++14 (gcc 8.3)
created:
287 days 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!