이 문제는 이것이 코딩테스트다. 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)
'Problem Solving > 최단 경로' 카테고리의 다른 글
BOJ1916 최소비용 구하기 (0) | 2023.03.30 |
---|---|
BOJ1446 지름길 (0) | 2023.03.21 |
BOJ18352 특정 거리의 도시 찾기 (0) | 2023.03.20 |
전보 (1) | 2023.01.20 |