ltpq_cses_message_routes
BFS with path tracingunknown
c_cpp
2 years ago
1.0 kB
5
Indexable
#include<bits/stdc++.h> using namespace std; const int MAX = (int) 1e5 + 100; vector<int> adj[MAX]; int dist[MAX], pre[MAX]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int num_nodes, num_edges; cin >> num_nodes >> num_edges; for (int i = 1; i <= num_edges; i++) { int from,to; cin >> from >> to; adj[from].push_back(to); adj[to].push_back(from); } fill(pre, pre + 1 + num_nodes, 0); //line 43 fill(dist, dist + 1 + num_nodes, -1); dist[1] = 1; queue<int> bfs; bfs.push(1); while (bfs.size()) { int cur = bfs.front(); bfs.pop(); for (int nxt : adj[cur]) if (dist[nxt] == -1) { dist[nxt] = dist[cur] + 1; pre[nxt] = cur; bfs.push(nxt); } } if (dist[num_nodes] == -1) cout << "IMPOSSIBLE"; else { cout << dist[num_nodes] << '\n'; vector<int> path; int node = num_nodes; for (; node != 0; node = pre[node]) path.push_back(node); reverse(path.begin(), path.end()); for (auto node : path) cout << node << ' '; } }
Editor is loading...