[BOJ] 11870. 플로이드2 (C++)

문제

n개의 도시가 있다.

한 도시에서 출발해 다른 도시에 도착하는 m개의 버스가 있다.

모든 도시의 쌍에 대해 최소 비용을 출력하고 갈 수 없는 경우에는 0을 출력

그 다음, 도시 간의 최소 비용에 포함되어 있는 도시의 개수와 경로를 출력, 갈 수 없는 경우에는 0 출력

생각할 것

1. 모든 도시에서 모든 도시로 가는 최소 비용을 구해야하므로 플로이드 워셜 알고리즘을 사용하기
2. 중간에 경로는 어떻게 구할까?
   1.  
   2. vector<int> route; void find_route(int i, int j, vector<vector<int>> via) { if (via[i][j] == 0) { route.push_back(i); route.push_back(j); return; } find_route(i, via[i][j], via); route.pop_back(); find_route(via[i][j], j, via); }

코드

#include <iostream>
#include <vector>

#define INF 1e9
using namespace std;

vector<int> route;

void find_route(int i, int j, vector<vector<int>> via) {
    if (via[i][j] == 0) {
        route.push_back(i);
        route.push_back(j);
        return;
    }
    find_route(i, via[i][j], via);
    route.pop_back();
    find_route(via[i][j], j, via);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M, A, B, C;
    cin >> N >> M;

    vector<vector<int>> adj(N + 1, vector<int>(N + 1, INF));
    vector<vector<int>> via(N + 1, vector<int>(N + 1, 0));
    for (int i = 0; i < M; i++) {
        cin >> A >> B >> C;
        adj[A][B] = min(adj[A][B], C);
    }

    // 플로이드 워셜
    for (int i = 1; i <= N; i++) adj[i][i] = 0;
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (adj[i][j] > adj[i][k] + adj[k][j]) {
                    adj[i][j] = adj[i][k] + adj[k][j];
                    via[i][j] = k; // i에서 j까지 가는 최단 경로가 경유하는 정점 중 가장 번호가 큰 정점
                }
            }
        }
    }

    // 최소 비용 출력
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (adj[i][j] == INF) cout << 0 << " ";
            else cout << adj[i][j] << " ";
        }
        cout << "\\n";
    }

    // 경로 출력
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (adj[i][j] == INF || adj[i][j] == 0) cout << 0 << "\\n"; // 경로가 없는 경우
            else {
                vector<int>().swap(route);
                find_route(i, j, via);
                cout << route.size() << " ";
                for (int r: route) {
                    cout << r << " ";
                }
                cout << "\\n";
            }
        }
    }

    return 0;
}