[백준] 11562 백양로 브레이크 python(pypy)

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

11562번: 백양로 브레이크

플로이드 와샬 알고리즘을 사용해서 풀면된다.

뒤집지 않고 갈수 있으면 0을 넣고 한번이라도 뒤집어야한다면 1을 넣어서 초기화한다.

이후 floyd-warshall 알고리즘(i에서 k를 거쳐 j를 가능 방법)을 사용해서 최솟값으로 갱신하면 된다.

 

import sys; input = sys.stdin.readline
def floyd_warshall(n, visit):
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                
                visit[i][j] = min(visit[i][j], visit[i][k] + visit[k][j])
    return visit

def main():
    n, m = map(int, input().split())
    INF = 250 * 250
    visit = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        u, v, b = map(int, input().split())
        visit[u][v] = 0
        visit[v][u] = 0 if b else 1

    for i in range(1, n + 1):
        visit[i][i] = 0
    floyd_warshall(n, visit)

    ans = ''
    for _ in range(int(input())):
        s, e = map(int, input().split())
        ans += '{}\n'.format(visit[s][e])
    print(ans)

if __name__ == '__main__':
    main()