[백준] 백양로 브레이크

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

11562번: 백양로 브레이크

플로이드-와샬을 활용하면 풀이가 가능한 문제입니다. a b사이의 간선이 양방향인 경우에는 dist 배열에 dist[a][b], dist[b][a]를 0으로 만들어주고 a b사이의 간선이 양방향이 아닌 경우에는 dist[a][b]=0, dist[b][a]=1을 넣어주면 됩니다. 이렇게 해주면 단방향 간선으로 양방향으로 바꾸는 효과가 생기게 됩니다. 따라서  a-b사이의 간선을 양방향으로 바꾸었을 때의 최소 변경회수가 자동으로 계산이 되게 됩니다.

 

import sys
#sys.stdin = open("input.txt", "r")
INT_MAX = sys.maxsize

input = sys.stdin.readline
n, m = tuple(map(int, input().split()))

dist = [
    [INT_MAX] * (n + 1)
    for _ in range(n + 1)
]

# i -> i 경로 초기화
for i in range(1, n + 1):
    dist[i][i] = 0

for _ in range(m):
    a, b, w = tuple(map(int, input().split()))

    if w == 0:
        dist[a][b] = 0
        dist[b][a] = 1
    else:
        dist[a][b] = 0
        dist[b][a] = 0

# 플로이드-와샬을 통해 모든 정점간의 도달가능한지를 체크해둔다.
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

q = int(input())
for _ in range(q):
    a, b = tuple(map(int, input().split()))
    print(dist[a][b])