[BAEKJOON] 11404 플로이드 (C++)

[ 문제 ]

Floyd-Warshall

↑개념을 모른다면 간단하게 익히고 오는것이 좋다!

플로이드

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

19952

7328

5358

42.574%

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

[ 조건 및 풀이 ]

(1) 버스의 노선은 다양하고 중복될 수 있다

(2) 시작도시와 도착도시가 같은경우는 없다 (자기자신으로 돌아오는길은 없다)

(3) 출발도시 → 도착도시까지 최소비용을 구하고, 갈수 없는경우 0을출력한다

위 3가지 조건을 토대로 Floyd공식을 사용해 풀이를 이어나가면된다.

 

간단하게 풀어쓰자면

버스의 노선은 초기에 접근 불가능한 수(INF근접수)로 초기화 해줘야한다.

버스의 노선은 다양하고 중복이될 수 있으므로, 입력되는 버스노선들 중 최소값만 가져가고

이후 Floyd적용 후에 INF인곳은 0으로 출력해주면 된다.

*INF를 LONG_MAX(=2147483647)로 해주지않는 이유는 cost부분에서 오류를 초래하기 때문

[ 핵심소스코드 / C++ ]

void floyd() {
    for (int k = 1; k <= c; k++)
        for (int y = 1; y <= c; y++)
            for (int x = 1; x <= c; x++)
                if (y != x && cost[y][x] > cost[y][k] + cost[k][x])
                    cost[y][x] = cost[y][k] + cost[k][x];
}

[ 전체소스코드 / C++ ] 

#include <iostream>
#include <string.h>
#pragma warning(disable:4996)
using namespace std;

#define endl "\n"
#define MAX 101
#define INF MAX*100001

int c, bus;
int cost[MAX][MAX];

void floyd() {
    for (int k = 1; k <= c; k++)
        for (int y = 1; y <= c; y++)
            for (int x = 1; x <= c; x++)
                if (y != x && cost[y][x] > cost[y][k] + cost[k][x])
                    cost[y][x] = cost[y][k] + cost[k][x];
}
void view() {
    for (int i = 1; i <= c; i++) {
        for (int j = 1; j <= c; j++) {
            if (cost[i][j] == INF) {
                cout << 0 << " ";
                continue;
            }
            cout << cost[i][j] << " ";
        }
        cout << endl;
    }
}
void init() {
    for (int i = 1; i <= c; i++)
        for (int j = 1; j <= c; j++)
            cost[i][j] = INF;
}
int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> c;
    cin >> bus;
    int start, end, value;
	
    init();
    for (int i = 0; i < bus; i++) {
        cin >> start >> end >> value;
        if (cost[start][end] > value)
            cost[start][end] = value;
    }
    floyd();
    view();
}