t_미래도시_259

📚 604 최단경로

문제

n의 회사 도로를 통해 연결되어 있다.
1번회사에 위해 있으며 k번방문 > x 번방문
도로는 정확히 1만큼의 시간으로 이동할 수 있다

답

출발지가 정해져있다. > 다익스트라다
라고 생각했지만 중간에 k > x 로 가는 일이있으니깐 훼이엿다 플로이드 워셜이였다.

# <span id="1번회사에-위해-있으며-k번방문-x-번방문-"></span>1번회사에 위해 있으며 k번방문 > x 번방문 

input = input.strip().split('\n')
x , k = map(int, input.pop().split())
n , m = map(int, input[0].split())

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

for i in range(1, len(input)):
    a,b = map(int,input[i].split())
    graph[a][b] = 1
    graph[b][a] = 1
    
for a in range(1,n+1):
    for b in range(1,n+1):
        for k in range(1,n+1):
            if a == b or b == k or a ==k:
                graph[b][b] = 0
                continue
            tmp = min(graph[a][b],graph[a][k]+graph[k][b])
            graph[a][b] = tmp
            graph[b][a] = tmp
sum = graph[1][k] + graph[k][x]
print(sum if sum < inf else -1)