Camí més curt

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> Graph;
typedef vector<bool> VB;
typedef queue<int> Queue;
typedef stack<int> Stack;

void shortestPath(const Graph &G, int i, int f, Stack& P) {
    VB S(G.size(), false); S[i] = true;
    Queue Q; Q.push(i);
    VI path(G.size());
    while (Q.front() != f) {
        int u = Q.front(); Q.pop();
        for (int arc : G[u]) {
            if (not S[arc]) {
                S[arc] = true;
                Q.push(arc);
                path[arc] = u;
            }
        }
    }
    P.push(f);
    while (P.top() != i) P.push(path[P.top()]);
}

void printStack(Stack &P) {
    cout << P.top(); P.pop();
    while (not P.empty()) {
        cout << ' ' << P.top(); P.pop();
    }
    cout << endl;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        Graph G(n, VI());
        for (int i = 0; i < m; ++i) {
            int x, y; cin >> x >> y;
            G[x].push_back(y);
        }
        for (VI &V : G) sort(V.begin(), V.end());
        Stack P;
        shortestPath(G, 0, n - 1, P);
        printStack(P);
    }
}