이번 문제는 플로이드-와샬 알고리즘을 통해 해결하였다. 데이터를 저장하는 방식에서 고민을 하였고, a-b가 양방향일 경우에는 way[a][b]와 way[b][a]를 모두 0으로 갱신시켜주었고, a-b가 단방향일 경우에는 way[a][b]만 1로 갱신해주었다. way에는 각 좌표로 가는데 필요한 바꾸는 횟수가 저장되는 것이다. 그리고 플로이드 와샬을 통해 i와 j가 같을 경우에는 way[i][j]를 0으로 갱신해주고, 그 외에는 way[i][j]를 way[i][j]와 d를 거쳐 가는 경우의 변경 횟수를 비교하여 더 작은 값을 취하도록 하였다. 이 과정이 끝나면 출발점과 도착점에 해당하는 way[출발점][도착점]을 바로 출력하도록 하였다.

Code

n, m = map(int, input().split())
way = [[1e9 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    way[a][b] = 0
    if c == 1:
        way[b][a] = 0
    else:
        way[b][a] = 1
for d in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j:
                way[i][j] = 0
            else:
                way[i][j] = min(way[i][j], way[i][d]+way[d][j])
k = int(input())
question = [list(map(int, input().split())) for _ in range(k)]
for a, b in question:
    print(way[a][b])