[파이썬] [최단경로] 백준 1956 운동

문제

https://www.acmicpc.net/problem/1956

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가 가장짧은것을 

구하면된다.