BOJ - 11562 - 백양로 브레이크

Updated:

import sys
_INF = 1e10

def solution():
    N, M = map(int, sys.stdin.readline().split())

    dist = [[_INF for j in range(N)] for i in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        U, V, B = map(int, sys.stdin.readline().split())
        if B == 1:
            dist[U-1][V-1] = 0
            dist[V-1][U-1] = 0
        else:
            dist[U-1][V-1] = 0
            dist[V-1][U-1] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i == j: continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    K = int(sys.stdin.readline())
    for _ in range(K):
        S, E = map(int, sys.stdin.readline().split())
        print(dist[S-1][E-1])

solution()

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

Categories:

Updated:

Leave a comment