BOJ 11780 플로이드 2

1 개요

BOJ 11780 플로이드 2

• 백준 온라인 저지 11780번 문제
• BOJ 34단계

2 같이 보기

• BOJ 11404 플로이드

3 C++

#include <bits/stdc++.h>
using namespace std;
 
int N, M;
int cost[110][110];
int route[110][110];
vector<int> v;
int INF = INT_MAX/2;

void floyd() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) continue;
                if (cost[i][j] > cost[i][k] + cost[k][j]) {
                    cost[i][j] = cost[i][k] + cost[k][j];
                    route[i][j] = k;
                }
            }
        }
    }
}
 
void findRoute(int s, int e) {
    if (route[s][e] == 0) {
        v.push_back(s);
        v.push_back(e);
        return;
    }
    findRoute(s, route[s][e]);
    v.pop_back();
    findRoute(route[s][e], e);
}
 
void solve() {
    floyd();
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (cost[i][j] == INF) {
                cout << 0 << ' ';
            } else {
                cout << cost[i][j] << ' ';
            }
        }
        cout << '\n';
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (cost[i][j] == INF) {
                cout << 0;
            } else {
                v.clear();
                findRoute(i, j);
                cout << v.size() << ' ';
                for (int k = 0; k < v.size(); k++) {
                    cout << v[k] << " ";
                }
            }
            cout << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cost[i][j] = INF;
        }
    }
    int a, b, c;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        cost[a][b] = min(cost[a][b], c);
    }
    solve();
}