반응형
1. 풀이
플로이드와샬의 정석
k 포문이 돌아갈때 L[i][j]의 의미 : k정점까지 사용이 가능할 때 i에서 j까지의 최단거리
* 초기화시 주의할점
L[i][j]가
(1) if i==j 이면 => 0
(2) if i!=j 이면 => inf
으로 초기화할것!
2. 소스코드
N,M=map(int,input().split())
maxNum=9876543210
L=[[maxNum for j in range(N+1)] for i in range(N+1)]
for i in range(1,M+1):
a,b=map(int,input().split())
L[a][b]=1
L[b][a]=1
for i in range(1,N+1):
L[i][i]=0
for k in range(1,N+1):
for i in range(1,N+1):
for j in range(1,N+1):
temp=L[i][k] + L[k][j]
if L[i][j]>temp:
L[i][j]=temp
ansNum=maxNum
ans=0
for i in range(1,N+1):
tempSum=sum(L[i][1:])
if tempSum<ansNum:
ansNum=tempSum
ans=i
print(ans)
반응형