fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. struct arco {
  10. 	int fine;
  11. 	int peso;
  12. };
  13.  
  14. void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long> &D) {
  15. 	vector<arco> list[N];
  16. 	D.resize(N);
  17. 	for(int i=0; i<N;  i++) D[i] = INT_MAX;
  18. 	// Build adjacency list
  19. 	for (int i = 0; i < M; i++) {
  20. 		arco tmp;
  21. 		tmp.fine = Y[i];
  22. 		tmp.peso = P[i];
  23. 		list[X[i]].push_back(tmp);
  24. 		D[X[i]] = -1;
  25. 		D[tmp.fine] = -1;
  26. 	}
  27. 	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  28. 	pq.push(make_pair(0, 0));
  29. 	D[0] = 0;
  30. 	while (!pq.empty()) {
  31. 		int nodo = pq.top().first;
  32.  
  33. 		pq.pop();
  34. 		for (arco next: list[nodo]) {
  35.  
  36. 			if (D[nodo] + next.peso < D[next.fine] || D[next.fine] == -1) {
  37. 				D[next.fine] = D[nodo] + next.peso;
  38. 				pq.push(make_pair(D[next.fine], next.fine));
  39. 			}
  40. 		}
  41. 	}
  42. }
  43.  
  44.  
  45. int main() {
  46.     int N, M;
  47.     cin >> N >> M;
  48.  
  49.     vector<int> X(M), Y(M), P(M);
  50.     vector<long long> D(N);
  51.  
  52.     for (int i = 0; i < M; i++) {
  53.         cin >> X[i] >> Y[i] >> P[i];
  54.     }
  55.  
  56.     mincammino(N, M, X, Y, P, D);
  57.  
  58.     for (int i = 0; i < N; i++) {
  59.         cout << D[i] << ' ';
  60.     }
  61.     cout << '\n';
  62. }
  63.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5 7
0 1 1
0 2 1
1 3 1
2 1 1
3 2 1
3 4 1
2 4 1
stdout
copy 
0 1 1 2 2
https://ideone.com/n40b7c
language:
C++ (gcc 8.3)
created:
2 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!