Message Routes

Solution by TioPatinhas — 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 u, v;
        cin >> u >> v; 
        u--, v--;
        vizinhos[v].push_back(u);
        vizinhos[u].push_back(v);
    }
    queue<int>Q;
    Q.push(0);
    vector<int>D(n, -1);
    D[0] = 0;
    vector<int>P(n, -1);
    while (!Q.empty()) {
        int v = Q.front();
        Q.pop();
        for (auto &x : vizinhos[v]) {
            if (D[x] == -1) {
                D[x] = D[v] + 1;
                Q.push(x);
                P[x] = v;
            }
        }
    }
    if (P[n-1] == -1) {cout << "IMPOSSIBLE";}
    else {cout << D[n-1] + 1 << endl;
    vector<int> path;
    int now = n-1;
    while (now != -1) {
        path.push_back(now);
        now = P[now];
    }
    for (int x = path.size()-1; x >= 0; x--) cout << path[x] + 1 << ' ';}
}

Last updated 3 weeks, 3 days ago

« Back to problem