fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl "\n"
  3. using namespace std;
  4. #define int long long int
  5. #define watch(x) cout << (#x) << " is " << (x) << "\n"
  6. #define watch2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << "\n"
  7.  
  8. int n, m;
  9. vector<set<pair<int,int>>> g;
  10. vector<int> dist;
  11. vector<int> par;
  12.  
  13. void dij()
  14. {
  15. 	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  16. 	pq.push({0,1});
  17. 	dist[1] = 0;
  18. 	par[1] = -1;
  19.  
  20. 	while(!pq.empty())
  21. 	{
  22. 		int u = pq.top().second;
  23. 		int d = pq.top().first;
  24. 		pq.pop();
  25.  
  26. 		if(dist[u] < d) continue;
  27.  
  28. 		for(auto e: g[u])
  29. 		{
  30. 			int v = e.first;
  31. 			int c = e.second;
  32. 			if(dist[v] > dist[u]+c)
  33. 			{
  34. 				dist[v] = dist[u]+c;
  35. 				pq.push({dist[v],v});
  36. 				par[v] = u;
  37. 			}
  38. 		}
  39.  
  40.  
  41. 	}
  42.  
  43. }
  44.  
  45. int32_t main()
  46. {
  47. 	ios_base::sync_with_stdio(false);
  48. 	cin.tie(NULL);
  49. 	cin >> n >> m;
  50. 	dist.resize(n+1);
  51. 	par.resize(n+1);
  52.  
  53. 	for(int i = 1; i <= n; ++i)
  54. 	{
  55. 		par[i] = -1;
  56. 	}
  57.  
  58. 	g.resize(n+1);
  59. 	for(int i = 0; i < m; ++i)
  60. 	{
  61. 		int u, v;
  62. 		cin >> u >> v;
  63. 		g[u].insert({v,-1});
  64. 	}
  65. 	dij();
  66. 	if(dist[n] == 0)
  67. 	{
  68. 		cout << "IMPOSSIBLE";
  69. 		return 0;
  70. 	}
  71.  
  72. 	cout << 1 + dist[n]*(-1) << endl;
  73. 	vector<int> ans;
  74. 	int temp = n;
  75. 	while(temp != -1)
  76. 	{
  77. 		ans.push_back(temp);
  78. 		temp = par[temp];
  79. 	}
  80. 	reverse(ans.begin(), ans.end());
  81. 	for(auto u: ans)
  82. 	{
  83. 		cout << u << " ";
  84. 	}
  85.  
  86. }
Runtime error #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QsHX3c
language:
C++14 (gcc 8.3)
created:
3 years 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!