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