[알고리즘] 백준 - 1613 - 역사

1.  문제

역사

2.  접근

1. n 의 범위가 500이 안되기에 플로이드가 가능함을 알 수 있다.

2. 일반적인 플로이드 - 워셜의 알고리즘으로 풀면 되는데, 체크 할점은 전후 사정이기에 a->b 이냐 b->a 이냐 아니면 모르냐 의 출력 과정만 조심하면 될거 같다

 

3.  풀이

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

INF = int(1e9)
graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(k):
    a, b = map(int, input().split())
    graph[a][b] = 1

for k in range(1, n+1):
    graph[k][k] = 0

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

s = int(input())
for i in range(s):
    a, b = map(int, input().split())

    if graph[a][b] != INF:
        print(-1)
    elif graph[b][a] != INF:
        print(1)
    else:
        print(0)