fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <queue>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int visited[100001];
  9. map<int,map<int,int> > Map;
  10. int prev1[100001];
  11.  
  12. int main() {
  13.  
  14. 	int n,m;
  15. 	cin>>n>>m;
  16.  
  17. 	for(int i=0;i<m;i++)
  18. 	{
  19. 		int x,y;
  20. 		cin>>x>>y;
  21. 		Map[x-1][y-1]=1;
  22. 		Map[y-1][x-1]=1;
  23. 	}
  24.  
  25. 	for(int i=0;i<n;i++)
  26. 	{
  27. 		visited[i]=0;
  28. 		prev1[i]=-1;
  29. 	}
  30.  
  31. 	queue<int> Q;
  32. 	Q.push(0);
  33. 	while(!Q.empty())
  34. 	{
  35. 		int x = Q.front();
  36. 		Q.pop();
  37. 		visited[x]=1;
  38. 		//cout<<x<<endl;
  39.  
  40. 		if(x == n-1)
  41. 		{
  42. 			break;
  43. 		}
  44.  
  45. 		/*for(int i=0;i<n;i++)
  46. 		{
  47. 			cout<<"visited["<<i<<"]="<<visited[i]<<endl;
  48. 		}
  49. 		cout<<endl;*/
  50.  
  51. 		for(auto it=Map[x].begin();it!=Map[x].end();it++)
  52. 		{
  53. 			//cout<<"----visited["<<it->first<<"]="<<visited[it->first]<<endl;
  54. 			if(visited[it->first] == 0)
  55. 			{
  56. 				visited[it->first]=1;
  57. 				Q.push(it->first);
  58. 				prev1[it->first] = x;
  59. 			}
  60. 		}
  61. 	}
  62.  
  63. 	/*for(int i=0;i<n;i++)
  64. 	{
  65. 		cout<<"prev["<<i<<"]="<<prev1[i]<<endl;
  66. 	}*/
  67.  
  68.  
  69.  
  70. 	if(prev1[n-1] == -1)
  71. 	{
  72. 		cout<<"IMPOSSIBLE"<<endl;
  73. 	}
  74. 	else
  75. 	{
  76. 		vector<int> ans;
  77. 		int i=n-1;
  78. 		while(i !=-1)
  79. 		{
  80. 			//cout<<"i="<<i<<endl;
  81. 			ans.push_back(i);
  82. 			i=prev1[i];
  83. 		}
  84.  
  85. 		reverse(ans.begin(),ans.end());
  86. 		cout<<ans.size()<<endl;
  87. 		for(int i=0;i<ans.size();i++)
  88. 		{
  89. 			cout<<ans[i]+1<<" ";
  90. 		}
  91. 		cout<<endl;
  92. 	}
  93. 	return 0;
  94. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
10 20
8 9
6 7
9 10
7 9
3 4
5 8
6 8
1 2
5 7
8 10
2 3
1 4
7 8
5 6
6 9
1 3
4 5
3 6
3 5
7 10
stdout
copy 
5
1 3 5 7 10
https://ideone.com/zRLBV1
language:
C++14 (gcc 8.3)
created:
8 days 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!