BOJ 1613 역사(Python 3)

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

플로이드 와샬 알고리즘은 단 4줄이기 때문에 외우기 굉장히 쉽다.

for k for i for j ,  ij, ikj 이렇게만 외우면 끝

플로이드를 돌린 후

서로 다른 두 사건의 번호가 주어질 때(만약 a,b라고 주어질 때)
D[a][b] != INF 이면 -1

D[b][a] != INF 이면 1

D[a][b] == INF 이면 0을 출력하면 된다.

Python으로 제출하면 시간 초과가 나기 때문에 Pypy로 제출 해야 한다.

코드 확인

n,m=map(int,input().split())
Max=float('inf')
S=[[Max]*(n+1) for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    S[a][b]=1
for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            S[i][j]=min(S[i][j], S[k][j]+S[i][k])
for i in range(int(input())):
    a,b=map(int,input().split())
    if S[a][b]!=Max: print(-1)
    elif S[b][a]!=Max: print(1)
    else: print(0)