(C++) - 백준(BOJ) 11404번 : 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

플로이드 와샬문제였습니다.

 

풀이방법

 1. 출발점과 도착점이 같은 입력이 여러번 주어질 수 있으므로 더 작은 가중치를 가진 도시를 인접행렬 dist배열에 저장해줍니다.

 

 2. 플로이드 와샬 알고리즘을 수행합니다. i -> k 도시로 가는 비용 + k -> j 도시로 가는 비용 보다 i -> j로 가는 비용이 크다면 갱신해줍니다.

 

 3. 각 도시로 가는 최소비용을 출력합니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int dist[101][101];
int n,m;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            dist[i][j] = INF;
    }

    for(int i = 0; i < m; i++){
        int start,end,weight;
        cin >> start >> end >> weight;
        if(dist[start][end] > weight)
            dist[start][end] = weight;
    }

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dist[i][j] == INF || i == j) cout << 0 << ' ';
            else cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }
}