BOJ 문제풀이/최단경로 (Shortest Path)

백준 11404 : 플로이드

DevJK 2018. 12. 6. 19:31

https://www.acmicpc.net/problem/11404


제목부터 플로이드다

플로이드-와샬 알고리즘을 알고있다면 그냥 n^3 한다음에

2차원배열을 출력하면 끝.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#define MAX 101
#define INF 1000000000   
using namespace std;

int matrix[MAX][MAX];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            matrix[i][j] = (i==j) ? 0:INF;
        }
    }
    while(m--){
        int a, b, w;
        cin >> a >> b >> w;
        if(matrix[a][b] > w){
            matrix[a][b] = w;
        }
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(matrix[i][j] > matrix[i][k] + matrix[k][j]){
                    matrix[i][j] = matrix[i][k] + matrix[k][j];
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(matrix[i][j] == INF)
                matrix[i][j] = 0;
            cout << matrix[i][j] << " ";
        }
        cout << '\n';
    }

    return 0;
}


저작자표시