fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12.  
  13. int n, m;  
  14. vector<int> adj[N]; 
  15.  
  16. bool vis[N]; 
  17. int p[N]; 
  18.  
  19. void bfs(int s) {
  20. 	for (int u = 1; u <= n; u++) {
  21. 		vis[u] = false;  
  22. 		p[u] = 0;  
  23. 	}
  24.  
  25. 	queue<int> q;  
  26. 	vis[s] = true;  
  27. 	q.push(s);  
  28.  
  29. 	while (!q.empty()) {
  30. 		int u = q.front(); q.pop(); 
  31.  
  32. 		for (int v : adj[u]) {
  33. 			if (!vis[v]) {
  34. 				vis[v] = true; 
  35. 				p[v] = u;  
  36. 				q.push(v); 
  37. 			}
  38. 		}
  39. 	}
  40. }
  41.  
  42. int main() {
  43. 	ios::sync_with_stdio(false); 
  44. 	cin.tie(nullptr); 	
  45. 	cin >> n >> m; 
  46.  
  47. 	for (int i = 0; i < m; i++) {
  48. 		int u, v; 
  49. 		cin >> u >> v; 
  50. 		adj[u].push_back(v); 
  51. 		adj[v].push_back(u); 
  52. 	}
  53.  
  54. 	bfs(1); 
  55.  
  56. 	if (!vis[n]) {
  57. 		cout << "IMPOSSIBLE" << '\n'; 
  58. 		return 0; 
  59. 	}
  60.  
  61. 	vector<int> path;  
  62. 	for (int u = n; u > 0; u = p[u]) path.push_back(u); 
  63.  
  64. 	reverse(path.begin(), path.end());  
  65.  
  66. 	cout << path.size() << '\n'; 
  67. 	for (int u : path) cout << u << ' '; 
  68. }
Success #stdin #stdout 0.01s 5980KB
comments (?)
stdin 
5 5
1 2
1 3
1 4
2 3
5 4
stdout 
3
1 4 5
https://ideone.com/VbCmLh
language:
C++14 (gcc 8.3)
created:
296 days ago
visibility:
secret

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!