미래도시

이 문제는 이것이 코딩테스트다. 259페이지 문제이다. 

이 문제는 E,V(간선,노드)가 100이하로 작다. 전형적인 플로이드 워셜문제이다.

일반적으로 500정도면 플로이드워셜을 사용하여도 된다.

 

아래는 나의코드이다.

 

import sys
INF = int(1e9)
companyNum,wayNum = map(int,sys.stdin.readline().split())
myMap= [[INF]*(companyNum+1) for _  in range(companyNum+1)]

for i in range(1,companyNum+1):
    myMap[i][i]=0


for _ in range(wayNum):
    temp=list(map(int,sys.stdin.readline().split()))
    myMap[temp[0]][temp[1]] = 1
    myMap[temp[1]][temp[0]] = 1

X ,K = map(int,sys.stdin.readline().split())


for i in range(1,companyNum+1):
    for j in range(1,companyNum+1):
        for k in range(1,companyNum+1):
            myMap[i][j] = min(myMap[i][j], myMap[i][k] + myMap[k][j])


result= myMap[1][K]+myMap[K][X]

if result>=INF:
    print(-1)
else:
    print(result)