[1719] 택배

https://www.acmicpc.net/problem/1719

1719번: 택배

플로이드+역추적

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, a[201][201], path[201][201];

constexpr int INF = 1e9;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    int i, j, k;

    for (i = 1; i <= n; i++)

        for (j = 1; j <= n; j++)

            if (i != j) a[i][j] = INF;

    for (i = 0; i < m; i++) {

        int A, B, C;

        cin >> A >> B >> C;

        a[A][B] = C;

        a[B][A] = C;

        path[A][B] = B;

        path[B][A] = A;

    }

    for (k = 1; k <= n; k++) {

        for (i = 1; i <= n; i++) {

            for (j = 1; j <= n; j++) {

                if (a[i][j] > a[i][k] + a[k][j]) {

                    a[i][j] = a[i][k] + a[k][j];

                    path[i][j] = path[i][k];

                }

            }

        }

    }

    for (i = 1; i <= n; i++) {

        for (j = 1; j <= n; j++) {

            if (i == j)

                cout << "- ";

            else

                cout << path[i][j] << ' ';

        }

        cout << '\n';

    }

    return 0;

}

---