vitormartinotti

Untitled

Oct 28th, 2025
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define MAXN 100010
  3.  
  4. using namespace std;
  5.  
  6. vector<int> grafo[MAXN];
  7.  
  8. queue<int> q;
  9. int marc[MAXN], dist[MAXN], pai[MAXN];
  10. int n;
  11.  
  12. void bfs(int s){
  13.     q.push(s);
  14.     marc[s] = 1;
  15.     dist[s] = 0;
  16.     pai[s] = -1;
  17.     while(!q.empty()){
  18.         int v = q.front();
  19.         q.pop();
  20.         for(int viz : grafo[v]){
  21.             if(marc[viz] == 0){
  22.                 marc[viz] = 1;
  23.                 q.push(viz);
  24.                 dist[viz] = dist[v]+1;
  25.                 pai[viz] = v;
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. int main(){
  32.     int m; scanf("%d %d", &n, &m);
  33.  
  34.     for(int i = 1; i <= m; i++){
  35.         int a, b; scanf("%d %d", &a, &b);
  36.         grafo[a].push_back(b);
  37.         grafo[b].push_back(a);
  38.     }
  39.     bfs(1);
  40.  
  41.     if(dist[n] == 0){
  42.         printf("IMPOSSIBLE\n");
  43.         return 0;
  44.     }
  45.     printf("%d\n", dist[n]+1);
  46.  
  47.     //Encontra o menor caminho da fonte até o vértice v
  48.     vector<int> path;
  49.     path.push_back(n);
  50.     while(pai[n] != -1){
  51.         n = pai[n];
  52.         path.push_back(n);
  53.     }
  54.     //path.push_back(n);
  55.  
  56.     reverse(path.begin(),path.end());
  57.  
  58.     for(auto v : path){
  59.         printf("%d ", v);
  60.     }
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment