백준 11404 번 : 플로이드

문제 링크 : https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

 문제 설명 

 

1. 도시의 갯수가 주어지고 그다음 줄에는 버스의 갯수가 주어짐

2. 그리고 그다음줄에 도시간 이동시 드는 버스비가 주어진다.

3. 각 도시에 다른도시로 이동하는 최소비용을 배열형식으로 출력.

 

 

 알고리즘 

 

1.제목부터 플로이드이다. 플로이드 와샬 알고리즘 사용해서풀면쉽게 풀린다 .

 

 코드 

 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int N, M, map[101][101];
    cin >> N >> M;
 
    //배열 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j)map[i][j] = 0;
            else map[i][j] = 1000000000;
        }
    }
 
    //간선 정보
    for (int j = 0; j < M; j++) {
        int a, b, c;
        cin >> a >> b >> c;
        map[a - 1][b - 1] = min(map[a - 1][b - 1], c);
 
    }
 
 
 
 
    //플로이드 와샬 알고리즘
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 1000000000) map[i][j] = 0;
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
       
 
 
}