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