Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define MAXN 100010
- using namespace std;
- vector<int> grafo[MAXN];
- queue<int> q;
- int marc[MAXN], dist[MAXN], pai[MAXN];
- int n;
- void bfs(int s){
- q.push(s);
- marc[s] = 1;
- dist[s] = 0;
- pai[s] = -1;
- while(!q.empty()){
- int v = q.front();
- q.pop();
- for(int viz : grafo[v]){
- if(marc[viz] == 0){
- marc[viz] = 1;
- q.push(viz);
- dist[viz] = dist[v]+1;
- pai[viz] = v;
- }
- }
- }
- }
- int main(){
- int m; scanf("%d %d", &n, &m);
- for(int i = 1; i <= m; i++){
- int a, b; scanf("%d %d", &a, &b);
- grafo[a].push_back(b);
- grafo[b].push_back(a);
- }
- bfs(1);
- if(dist[n] == 0){
- printf("IMPOSSIBLE\n");
- return 0;
- }
- printf("%d\n", dist[n]+1);
- //Encontra o menor caminho da fonte até o vértice v
- vector<int> path;
- path.push_back(n);
- while(pai[n] != -1){
- n = pai[n];
- path.push_back(n);
- }
- //path.push_back(n);
- reverse(path.begin(),path.end());
- for(auto v : path){
- printf("%d ", v);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment