[BOJ 11404 // C++] 플로이드

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11404번 문제인 플로이드이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11404

11404번: 플로이드

이 문제는 플로이드-워셜(Floyd-Warshall) 알고리즘을 연습하는 문제이다.

단, 문제와 예제에 있듯이 한 도시에서 다른 도시로 연결하는 간선이 여러개일 수 있음을 유의해야 한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::min;
using std::cin;
using std::cout;

int city[101][101];

int main()
{
    int N, M;
    cin >> N >> M;
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= N;j++) {
            if (i == j) city[i][j] = 0;
            else city[i][j] = 1000000001;
        }
    }
    for (int i = 0;i < M;i++) {
        int s, e, w;
        cin >> s >> e >> w;
        city[s][e] = min(city[s][e], w); // 입력을 받을 때, 가장 비용이 적은 노선만 입력받는다.
    }
    for (int m = 1;m <= N;m++) { // Floyd-Warshall
        for (int i = 1;i <= N;i++) {
            for (int j = 1;j <= N;j++) {
                city[i][j] = min(city[i][j], city[i][m] + city[m][j]);
            }
        }
    }
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= N;j++) {
            cout << ((city[i][j] == 1000000001) ? 0 : city[i][j]) << ' ';
        }
        cout << "\n";
    }
    return 0;
}