Dunamic programming

shortest_path.cpp

#include <bits/stdc++.h>

using namespace std;

/*
 * Cho đồ thị vô hướng G có N đỉnh (N≤1000) và các cạnh có trọng số dương.
 * Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh N hoặc thông báo không tồn tại đường đi.
 * Simple input
 * 5
 * 0 1 1 5 5
 * 1 0 0 1 0
 * 1 0 0 1 3
 * 5 1 1 0 1
 * 5 0 3 1 0
 *
 * Output
 * 3
 * 4 3 1
 */

void sol() {
    int n;
    cin >> n;
    int C[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) cin >> C[i][j];
    }

    int F[n], T[n+1];
    memset(F, 999999, sizeof(F));
    memset(T, 0, sizeof(T));
    F[0] = 0;
    for (int i = 1; i < n; ++i) {
        int jmin = i;
        for (int j = 0; j < n; ++j) {
            if (C[j][i] && F[jmin] + C[jmin][i] > C[j][i] + F[j]) {
                jmin = j;
            }
        }
        F[i] = C[jmin][i] + F[jmin];
        T[i] = jmin;
    }

    if (F[n-1] == 999999) {
        cout << "Impossible\n";
    }
    else {
        cout << F[n-1] << "\n";
        int i = n-1;
        while (i > 0) {
            cout << i << " ";
            i = T[i];
        }
    }
}


int main() {
    cin.sync_with_stdio(0);
    cin.tie(nullptr);
    ifstream in("in.txt");
    ofstream out("out.txt");
    streambuf *cinbuf = cin.rdbuf();
    streambuf *coutbuf = cout.rdbuf();
    cin.rdbuf(in.rdbuf());
    cout.rdbuf(out.rdbuf());
    sol();
    cin.rdbuf(cinbuf);
    cout.rdbuf(coutbuf);
    return 0;
}