Message Routes

Solution by Mr.Olimpia — 100 pts

Code / Notes

#include <bits/stdc++.h>
using namespace std;

// https://ide.usaco.guide/Ov5Bu8j7yJ_6itiOaT2

// P[3] = 5 -> o pai do 3 é o 5
// P[3] = -1 -> 3 não tem pai

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[u].push_back(v);
        vizinhos[v].push_back(u);
    }
    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";
        exit(0);
    }
    vector<int> path;
    int x=n-1;
    while(x!= -1){
        path.push_back(x);
        x=P[x];
    }
    cout << path.size() << endl;
    for(int i=path.size()-1; i>=0; i--){
        cout << path[i]+1 << " ";
    }
}

Last updated 1 month, 3 weeks ago

« Back to problem