백준 10159 : 저울

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; }