fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. vector<int> used, dist, par;
  6. vector<vector<pair<int,int> > > g;
  7. int n, inf=1e9;
  8. void dijkstra(int v){
  9. 	dist[v]=0;
  10. 	int mn=0;
  11. 	while(mn!=inf){
  12. 		used[v]=1;
  13. 		for(auto [x,y]:g[v]){
  14. 			if(dist[x]>dist[v]+y){
  15. 				dist[x]=dist[v]+y;
  16. 				par[x]=v;
  17. 			}
  18. 		}
  19. 		mn=inf;
  20. 		for(int i=0;i<n; i++){
  21. 			if (dist[i]<mn && !used[i]){
  22. 				mn=dist[i];
  23. 				v=i;
  24. 			}
  25. 		}
  26.  
  27. 	}
  28. }
  29. int main() {
  30. 	int s,f;
  31. 	cin>>n>>s>>f;
  32. 	s--;f--;
  33. 	used.assign(n,0);
  34. 	dist.assign(n,inf);
  35. 	par.assign(n,-1);
  36. 	g.resize(n);
  37. 	for(int i=0; i<n; i++)
  38. 		for(int j=0; j<n; j++){
  39. 			int x;
  40. 			cin>>x;
  41. 			if(x!=-1 && i!=j){
  42. 				g[i].push_back({j,x});
  43.  
  44. 			}
  45. 		}
  46. 	dijkstra(s);
  47. 	if(dist[f]==inf) cout<<-1;
  48. 	else{
  49. 		vector<int>ans;
  50. 		while(f!=-1){
  51. 			ans.push_back(f);
  52. 			f=par[f];
  53. 		}
  54. 		reverse(ans.begin(), ans.end());
  55. 		for(int x:ans){
  56. 			cout<<x+1<<" ";
  57. 		}
  58. 	}
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
3 2 1
0 1 1
4 0 1
2 1 0
stdout
copy 
2 3 1
https://ideone.com/Nnk2kf
language:
C++14 (gcc 8.3)
created:
3 hours 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!