Message Routes

Solution by dudu — 100 pts

Code / Notes

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N, M;
    cin >> N >> M;
 
    vector<vector<int>> vizinhos(N);
    for (int i = 0; i < M; i++) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        vizinhos[v].push_back(u);
        vizinhos[u].push_back(v);
    }
 
    vector<int> D(N, -1);
    vector<int> P(N, -1);
    queue<int> Q;
 
    D[0] = 0;
    Q.push(0);
 
    while (not Q.empty()) {
        int v = Q.front();
        Q.pop();
        for (auto u : vizinhos[v]) {
            if (D[u] == -1) {
                D[u] = D[v] + 1;
                P[u] = v;
                Q.push(u);
            }
        }
    }
 
    if (D[N-1] == -1) {
        cout << "IMPOSSIBLE" << endl;
        exit(0);
    }
 
    vector<int> path;
    int now = N-1;
    while (now != -1) {
        path.push_back(now);
        now = P[now];
    }
 
    cout << path.size() << endl;
    for (int i = path.size()-1; i >= 0; i--) {
        cout << path[i]+1 << ' ';
    }
}

Last updated 1 month ago

« Back to problem