BOJ #1613 - 역사

https://icpc.me/1613

# 문제 분류
최단 경로 찾기 (Floyd-Warshall Algorithm)

풀이 접근 방법 :

 

1. 각 노드쌍에 대한 최단 경로를 모두 구해야 하므로 역시 Floyd-Warshall 알고리즘을 사용하면 된다.

2. INF와 0으로 각각 초기화 한 후, dist[i][j]가 INF, 즉 갱신되지 않았다면 선후관계가 성립하지 않는다.

3. 즉, dist[i][j] != INF이면 i → j, dist[j][i] != INF이면 j → i, 둘 다 INF라면 선후관계를 파악할 수 없는 케이스이다.

---

얍.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
 
using namespace std;
 
int INF = 1e9;
int n, k, a, b, s;
int arr[410][410];
 
int main(){
    for(int i=0; i<410; i++){
        for(int j=0; j<410; j++){
            arr[i][j] = INF;
            arr[j][j] = 0;
        }
    }
 
    scanf("%d %d", &n, &k);
    for(int i=0; i<k; i++) {
        scanf("%d %d", &a, &b);
        arr[a][b] = 1;
    }
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++){
                arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
            }
        }
    }
 
    scanf("%d", &s);
    for(int i=0; i<s; i++){
        scanf("%d %d", &a, &b);
        if(arr[a][b] != INF) printf("-1\n");
        else if(arr[b][a] != INF) printf("1\n");
        else printf("0\n");
    }
 
    return 0;
}