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

백준 10159 : 저울

DevJK 2018. 12. 6. 19:58

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


백준 1613 : 역사 문제와 원리가 동일한 플로이드-와샬 알고리즘이다.


 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 n, m;
int matrix[MAX][MAX];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    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;
        cin >> a >> b;
        matrix[a][b] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                if(matrix[j][k] > matrix[j][i] + matrix[i][k]){
                    matrix[j][k] = matrix[j][i] + matrix[i][k];
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int count = 0;
        for(int j = 1; j <= n; j++){
            if(i==j) continue;
            if(!(matrix[i][j] != INF || matrix[j][i] != INF)){
                count++;
            }
        }
        cout << count << '\n';
    }

    return 0;
}


저작자표시 (새창열림)