[백준 11562번] 백양로 브레이크 - python

문제 링크

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

11562번: 백양로 브레이크

 

풀이

- 플로이드 워셜 사용 

일방향일 때는 지나갈 때의 비용을 1(통로 건설 개수)로 설정하고, 지나갈 수 있을 때는 0으로 설정하여 최단거리를 구해주면 된다. 

- 플로이드 워셜이라 pypy3으로 실행 

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

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

for _ in range(m):
    a, b, c = map(int,input().split())
    if c == 0 :
        graph[a][b] = 0
        # 일방통행이므로 지나가는데 드는 비용이 1 
        graph[b][a] = 1 
    else:
        graph[a][b] = 0
        graph[b][a] = 0 
  
# 자기 자신으로 가는 비용 0으로 초기화 
for i in range(1,n+1) :
    for j in range(1,n+1):
        if i == j :
            graph[i][j] = 0 
     
# 최소 통로 건설 개수 구하기 
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
          
k = int(input())
for _ in range(k):
    x, y = map(int,input().split())
    print(graph[x][y])