문제 설명

• 도시에서 도시까지의 최단거리를 구하는 문제
• 각 도시간에 연결 도로는 단방향으로 주어짐
  • 이 때 가중치(비용) 또한 주어짐
  • 시작 도시와 도착 도시가 같은 경우는 없음
• 출력 : 각 정점에서 정점까지 갈 수 있는 최소 비용 출력

문제 해결 KEY_POINT

• 플로이드-워셜
• 그래프

문제 해결 아이디어

• 입력을 받고 자기 자신신의 경로는 0으로 초기화
• 간선 입력
  • 시작, 도착, 가중치 입력
  • 만약 같은 시작과 끝을 가진 간선 존재시 작은 값으로 입력
• 플로이드-워셜 알고리즘 사용
• 결과 출력

소스 코드

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

const int INF = 2147483647; // 무한대를 의미하는 값

int main() {
    int city_num = 0, vertex_num = 0;
    cin >> city_num >> vertex_num;
    
    // 1-indexed로 사용할 것이므로 city_num+1 크기로 할당
    vector<vector<int>> matrix(city_num+1, vector<int>(city_num+1, INF));
    
    // 자기 자신으로의 경로는 0으로 초기화
    for (int i = 1; i <= city_num; i++) {
        matrix[i][i] = 0;
    }
    
    // 간선 입력
    for (int i = 0; i < vertex_num; i++) {
        int start = 0, end = 0, value = 0;
        cin >> start >> end >> value; // 시작 정점, 끝 정점, 가중치
        // 여러 간선이 있을 경우 더 작은 값 선택 (문제에 따라)
        matrix[start][end] = min(matrix[start][end], value);
    }
    
    // 플로이드-워셜 알고리즘 (1-indexed)
    for (int k = 1; k <= city_num; k++) {
        for (int i = 1; i <= city_num; i++) {
            for (int j = 1; j <= city_num; j++) {
                if (matrix[i][k] != INF && matrix[k][j] != INF) {
                    matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
                }
            }
        }
    }
    
    // 결과 출력
    for (int i = 1; i <= city_num; i++) {
        for (int j = 1; j <= city_num; j++) {
            if (matrix[i][j] == INF)
                cout << "0" << " ";  // 연결이 안 되어 있으면 0 출력 (문제 요구에 따라 조정)
            else
                cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

소감

플로이드 워셜은 신이야!