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, long long>>> lista(N);
  12. 	vector<bool> visited(N);
  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.  
  21. 	D[0]=0;
  22. 	visited[0]=false;
  23. 	for(int i=1; i<N; i++)
  24. 	{
  25. 		visited[i]=false;
  26. 		D[i]=LLONG_MAX;
  27. 	}
  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().first;
  37. 		long long dist=pq.top().second;
  38. 		pq.pop();
  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.  
  59. int main() {
  60.     int N, M;
  61.     cin >> N >> M;
  62.  
  63.     vector<int> X(M), Y(M), P(M);
  64.     vector<long long> D(N);
  65.  
  66.     for (int i = 0; i < M; i++) {
  67.         cin >> X[i] >> Y[i] >> P[i];
  68.     }
  69.  
  70.     mincammino(N, M, X, Y, P, D);
  71.  
  72.     for (int i = 0; i < N; i++) {
  73.         cout << D[i] << ' ';
  74.     }
  75.     cout << '\n';
  76. }
  77.  
  78.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
2 1
1 0 1
stdout
copy 
0 -1
https://ideone.com/aPYHpr
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!