[최단 경로] 9 - 2 미래 도시

공중미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다.

방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다.

연결된 두 회사는 양방향으로 이동할 수 있고, 연결된 도로는 1만큼의 시간으로 이동한다.

A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다.

A가 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하시오.

 

예를 들어 n = 5, x = 4, k =5 이고 회사 간 도로가 7개면서 각 도로가 다음과 같이 연결되어 있다.

(1, 2), (1, 3), (1, 4), (2, 4), (3, 4), (3, 5), (4, 5)

이때 A가 4번 회사에 가는 경로는 (1 - 3 - 5 -4) 로 설정하면 최소 이동시간은 3이다.

 

입력 조건

• 첫째 줄에 전체 회사의 개수 N과 경로의 수  M이 공백으로 구분되어 차례대로 주어진다. (1<=N,M<=100
• 둘째 줄부터 M+1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.
• M+2번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다. (1<=K<=100)

출력 조건 

• 첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.
• 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

입력 예시 1

5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5

 

출력 예시 1

3

 

입력 예시 2

4 2

1 3

2 4

3 4

 

출력 예시 2 

-1

 

 

---

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 노드 개수, 간선 개수 입력받기
n, m = map(int, input().split())

# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
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):
    # A와 B가 서로에게 가는 비용은 1이라고 설정
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

# 거쳐 갈 노드 X와 최종 목적지 노드 K를 입력받기
x, k = map(int, input().split())

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
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])

distance = graph[1][k] + graph[k][x]

# 도달할 수 없는 경우 -1 출력
if distance >= INF:
    print(-1)
else:
    print(distance)