Niloy007

Shortest path using BFS

May 16th, 2021
645
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define mx (int) 10000
  3. #define mem(a, b) memset(a, b, sizeof(a))
  4. using namespace std;
  5.  
  6. vector<int> adj[mx];
  7. int level[mx];
  8. vector<int> parent(mx, -1);
  9.  
  10. void bfs(int s) {
  11.     level[s] = 0;
  12.     queue<int> q;
  13.     q.push(s);
  14.     while (!q.empty()) {
  15.         int u = q.front();
  16.         q.pop();
  17.         for (auto v : adj[u]) {
  18.             if (level[v] == -1) {
  19.                 level[v] = level[u] + 1;
  20.                 q.push(v);
  21.                 parent[v] = u;
  22.             }
  23.         }
  24.     }
  25. }
  26.  
  27. int main() {
  28.     mem(level, -1);
  29.  
  30.     int n, e;
  31.     cin >> n >> e;
  32.     for (int i = 0; i < e; i++) {
  33.         int u, v;
  34.         cin >> u >> v;
  35.         adj[u].push_back(v);
  36.         adj[v].push_back(u);
  37.     }
  38.     int source, dest;
  39.     cin >> source >> dest;
  40.    
  41.     bfs(source);
  42.  
  43.     if (level[dest] == 0) {
  44.         cout << "No route\n";
  45.         return 0;
  46.     }
  47.  
  48.     vector<int> ans;
  49.     ans.push_back(dest);
  50.     while (parent[dest] != -1) {
  51.         ans.push_back(parent[dest]);
  52.         dest = parent[dest];
  53.     }
  54.  
  55.     reverse(ans.begin(), ans.end());
  56.  
  57.     for (auto u : ans) {
  58.         cout << u << " ";
  59.     }
  60.     cout << endl;
  61. }
  62.  
  63.  
RAW Paste Data