문제
https://www.acmicpc.net/problem/1956
코드
import heapq
import sys
INF=sys.maxsize
input=sys.stdin.readline
def dijk(start):
dis = [INF] * (v + 1)
q=[]
heapq.heappush(q,(0,start))
while q:
cost,node=heapq.heappop(q)
if cost>dis[node]:
continue
for i in graph[node]:
new_cost=cost+i[1]
if new_cost<dis[i[0]]:
dis[i[0]]=new_cost
heapq.heappush(q,(new_cost,i[0]))
return dis[start]
v,e=map(int, input().split())
graph=[[] for _ in range(v+1)]
for _ in range(e):
a,b,c=map(int, input().split())
graph[a].append((b,c))
result=INF
for i in range(v):
if dijk(i)!=INF:
result=min(dijk(i),result)
if result==INF:
print(-1)
else:
print(result)
생각 정리
import sys
V,E=map(int,sys.stdin.readline().split())
INF=sys.maxsize
matrix=[[INF for _ in range(V+1)] for _ in range(V+1)]
for _ in range(E):
a,b,c=map(int,sys.stdin.readline().split())
matrix[a][b]=c#a->b가는 거리 c
for k in range(1,V+1):#플로이드 와샬 k노드를 거쳐갈때
for i in range(1,V+1):
for j in range(1,V+1):
matrix[i][j]=min(matrix[i][j],matrix[i][k]+matrix[k][j])
result=INF
for i in range(1,V+1):#돌아오는 사이클 중 가장 최소거리 찾기
result=min(result,matrix[i][i])
if result==INF:
print(-1)
else:
print(result)
사이클이 될수있는 구간중 가장 짧은 경로 구하는것이다.
시작지점이 정해지지 않았고 모든구간에서 확인해야 하기때문에 플로이드 와샬을
이용해 모든 정점에서 모든 정점으로 가는 최소 거리를 구한뒤 i->i가 가장짧은것을
구하면된다.
'문제풀이 > 최단경로' 카테고리의 다른 글
[파이썬] [최단경로] 백준 9370 미확인 도착지 (0) | 2022.03.27 |
---|---|
[파이썬] [최단경로] 백준 14938 서강그라운드 (0) | 2022.03.16 |
[파이썬] [최단경로] 백준 1504 특정한 최단 경로 (0) | 2022.02.26 |
[파이썬] [최단경로] 백준 11657 타임머신 (0) | 2022.02.09 |
[파이썬] [최단경로] 벨먼포드 (0) | 2022.02.09 |