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

 

10159번: 저울

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

www.acmicpc.net

3중 포문으로 플로이드 와샬 알고리즘을 사용하였습니다.

 

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define INF 1e9
#define MAX_N 101
 
int dp[MAX_N][MAX_N];
int dp2[MAX_N][MAX_N];
int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N, Q;
     cin >> N >> Q;
     for (int i = 0; i <= N; i++) {
          for (int j = 0; j <= N; j++) {
               dp[i][j] = INF;
               dp2[i][j] = INF;
               if (i == j) {
                    dp[i][j] = 0;
                    dp2[i][j] = 0;
               }
          }
     }
     for (int i = 0; i < Q; i++) {
          int a, b; cin >> a >> b;
          dp[a][b] = 1;
          dp2[b][a] = 1;
     }
 
     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if (dp[s][m] != INF && dp[m][e] != INF)
                         dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e]);
               }
          }
     }
 
     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if (dp2[s][m] != INF && dp2[m][e] != INF)
                         dp2[s][e] = min(dp2[s][e], dp2[s][m] + dp2[m][e]);
               }
          }
     }
 
     int num = -1;
     for (int i = 1; i <= N; i++) {
          int tmp_ans = 0;
          for (int j = 1; j <= N; j++) {
               if (j == i) continue;
               if (dp[i][j] == INF && dp2[i][j] == INF) tmp_ans++;
          }
          cout << tmp_ans << "\n";
     }
}

 

 

저작자표시

'알고리즘 > [C++]BOJ' 카테고리의 다른 글

[백준BOJ] 9205 맥주 마시면서 걸어가기  (0) 2019.10.06
[백준BOJ] 1389 케빈 베이컨의 6단계 법칙  (0) 2019.10.05
[BOJ백준] 11657 타임머신  (0) 2019.10.05

+ Recent posts

티스토리툴바