BOJ - 11562

백준 문제 링크
백양로 브레이크

❓접근법

1. 플로이드 워셜 알고리즘을 활용했다.
2. 자기 자신에게 가는 비용은 0으로 지정하고,
   u, v, b를 받아준다.

• 일방통행 길일 때 (b == 0)
  graph[u][v] = 0, graph[v][u] = 1
• 양방향 길일 때 (b == 1)
  graph[u][v] = 0, graph[v][u] = 0

3. 3중 반복문으로 최단거리 테이블을 갱신한다.
4. k번 동안 학생들의 질문을 받고
   해당하는 인덱스를 graph에서 출력하면 끝!

👌🏻코드

n, m = map(int, input().split())

INF = int(1e9)

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    
    u, v, b = map(int, input().split())
    
    if b == 0: # 일방통행 길일 때
        graph[u][v] = 0 # u -> v는 설치할 필요 없음
        graph[v][u] = 1 # v -> u는 1개 설치
        
    elif b == 1: # 양방향 길일 때 
        graph[u][v] = 0 # u -> v는 설치할 필요 없음
        graph[v][u] = 0 # v -> u는 설치할 필요 없음
        
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b] , graph[a][k] + graph[k][b])
            
k = int(input())

for _ in range(k):
    
    a, b = map(int, input().split())
    
    print(graph[a][b])