message_route_1667.cpp (969B)
1 #include <iostream> 2 #include <queue> 3 #include <ranges> 4 #include <vector> 5 6 constexpr size_t inf = 1999999999; 7 8 int main() { 9 size_t n, m; 10 std::cin >> n >> m; 11 std::vector<std::vector<size_t>> a(n); 12 for (size_t i = 0; i < m; i++) { 13 size_t x, y; 14 std::cin >> x >> y; 15 a[x-1].push_back(y-1); 16 a[y-1].push_back(x-1); 17 } 18 19 std::queue<size_t> q; 20 std::vector<size_t> d(n, inf); 21 d[0] = 0; 22 q.push(0); 23 while (!q.empty()) { 24 auto i = q.front(); 25 q.pop(); 26 if (i == n-1) break; 27 for (auto j : a[i]) { 28 if (d[j] > d[i]+1) { 29 d[j] = d[i] + 1; 30 q.push(j); 31 } 32 } 33 } 34 35 if (d[n-1] == inf) { 36 std::cout << "IMPOSSIBLE\n"; 37 } else { 38 std::cout << d[n-1]+1 << "\n"; 39 // Backtracking 40 std::vector<size_t> v; 41 v.push_back(n-1); 42 while (v.back() != 0) { 43 for (auto j : a[v.back()]) { 44 if (d[j] == d[v.back()]-1) { 45 v.push_back(j); 46 break; 47 } 48 } 49 } 50 for (auto x : v | std::views::reverse) 51 std::cout << x+1 << " "; 52 std::cout << "\n"; 53 } 54 }