동빈북 미래도시 파이썬

문제
방문원 A는 시작점 1번회사에 있고 K번에 있는 사람과 소개팅을 한다고 한다.

그리고 방문원 A는 X 회사로 가야한다.

이 때, 총 N개의 도시와 M개의 도로가 주어질 경우 A가 갈 경로의 최단 거리를 구하라

 

입력

첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다(1<= N, M<=100)

둘째 줄부터 M+1 번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.

M+2번 째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다 (1<= K <= 100)

 

 

출력

첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.

만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

 

 

 

풀이 방식

일단 노드 범위가 100이하다. 플로이드 워셜을 대놓고 써달라는 느낌이다.

 

변수로는

n,m
회사 번호 graph 배열
distance 배열
x,k

이렇게 썼고,

1 -> k -> x 로 이동하는 최소값을 구해야 하는데, 반드시 k와 x를 지나가야 하므로

graph[1][k]+graph[k][x]를 구해주면 된다.

어차피 graph[1][k] , graph[k][x] 둘다 알고리즘에 의해 최소값이 된다. 

 

실수한 부분은 양방향이라서 거리를 추가할 때 반대로도 넣어주었어야 하는 부분이었다.

 

 

풀이

 

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
INF=1e9#추가
graph=[ [INF] * (n+1) for _ in range(n+1)]

for i in range(n+1):
    graph[i][i]=0

for _ in range(m):
    s,e=map(int,input().split())
    graph[s][e]=1
    graph[e][s] = 1 #양방향이라서 추가해줘야댐. 그래프같은 느낌
x,k=map(int,input().split())
print(x,k)
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])

distance=graph[1][k]+graph[k][x]
if distance==INF:
    print(-1)
else:
    print(distance)