fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. // Declaring functions
  7. void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D);
  8.  
  9. struct struttura{
  10. 	vector<pair<int, int>> collegamenti; 
  11. 	int entrata = 0; 
  12. 	bool passato = false; 
  13. 	bool collegatoazero = false; 
  14. }; 
  15.  
  16. void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D) {
  17. 	vector<struttura> nodo(N);
  18. 	pair<int, int> a; 
  19. 	nodo[0].collegatoazero = true; 
  20. 	for(int i = 0; i < M; i++){
  21. 		nodo[Y[i]].entrata++; 
  22. 		a.first = Y[i]; 
  23. 		a.second = P[i];  
  24. 		nodo[X[i]].collegamenti.push_back(a); 
  25. 		if(nodo[X[i]].collegatoazero) nodo[Y[i]].collegatoazero; 
  26. 	}
  27.  
  28. 	int posizionetop = 0; 
  29. 	D[0] = 0; 
  30. 	while(posizionetop < N){
  31.  
  32. 		for(int i = 0; i < N; i++){
  33. 			if(nodo[i].entrata == 0){
  34. 				for(int l = 0; l < nodo[i].collegamenti.size(); l++){
  35. 					//cout << i  << " : i " << D[i] << " : COSTO I " << nodo[i].collegamenti[l].first << ": PEKO PAIN " << D[i] + nodo[i].collegamenti[l].second << " : COSTO"<< endl;
  36. 					nodo[nodo[i].collegamenti[l].first].entrata--;
  37. 					if(nodo[i].collegatoazero && (nodo[nodo[i].collegamenti[l].first].passato == false || D[nodo[i].collegamenti[l].first] > D[i] + nodo[i].collegamenti[l].second)){
  38. 						D[nodo[i].collegamenti[l].first]= D[i] + nodo[i].collegamenti[l].second; 
  39. 						nodo[nodo[i].collegamenti[l].first].passato = true; 
  40. 						nodo[nodo[i].collegamenti[l].first].collegatoazero = true; 
  41. 					}
  42. 				} 
  43. 				nodo[i].entrata = -1; 
  44. 				break; 
  45. 			}
  46. 		}
  47. 		posizionetop++; 
  48. 	}
  49. 	/*for(int i = 0; i < N; i++){
  50. 		cout << nodo[i].passato << endl; 
  51. 	}*/
  52. 	D[0] = 0; 
  53. 	for(int i = 1; i < N; i++) if(nodo[i].passato == false) D[i] = -1; 
  54. }
  55.  
  56. int main() {
  57.     ios::sync_with_stdio(false);
  58.  
  59.     // Uncomment the following lines if you want to read/write from files
  60.     // ifstream cin("input.txt");
  61.     // ofstream cout("output.txt");
  62.  
  63.     // Reading input
  64.     int N, M;
  65.     cin >> N >> M;
  66.  
  67.     vector<int> X(M), Y(M), P(M), D(N);
  68.     for (int i = 0; i < M; i++) {
  69.         cin >> X[i] >> Y[i] >> P[i];
  70.     }
  71.  
  72.     // Calling functions
  73.     mincammino(N, M, move(X), move(Y), move(P), D);
  74.  
  75.     // Writing output
  76.     for (int i = 0; i < N; i++) {
  77.         cout << D[i] << ' ';
  78.     }
  79.     cout << '\n';
  80.  
  81.  
  82. }
  83.  
Success #stdin #stdout 0.01s 5336KB
comments (?)
stdin
copy 
1
1 0 1
stdout
copy 
0
https://ideone.com/CuVNbn
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!