[백준 1956번] 운동 - python

문제 링크

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

풀이 

- 다익스트라 풀이 

다익스트라로 출발지마다 다른 마을까지의 최단 거리를 구하고 자기 자신까지의 최솟값을 갱신해주었다.

그러다 python3으로는 시간 초과가 발생하고, pypy3으로만 통과 ㅠㅠ 

import heapq 
import sys
input = sys.stdin.readline 

INF = int(1e9)
def dijkstra(start):
	# 여기서 자기 자신까지의 거리르 0으로 초기화하면 안됨 
    distance= [INF] * (v+1)
    
    q = []
    heapq.heappush(q, (0,start))
    
    while q :
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue
        
        for i in graph[now]:
            cost = dist + i[1]
            
            if cost < distance[i[0]] :
                distance[i[0]] = cost 
                heapq.heappush(q, (cost, i[0]))
                
    return distance[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(1,v+1):
    result = min(result, dijkstra(i))

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

- 다른 블로그를 참고하니 한번의 다익스트라로 답을 구할 수 있었다. 

import heapq 
import sys
input = sys.stdin.readline 

INF = int(1e9)

v, e = map(int,input().split())    

graph = [ [] for _ in range(v+1) ]
# distance[i][j] 는 i에서 j로 가는 최단 거리 
distance= [ [INF] * (v+1) for _ in range(v+1) ]
q = []
    
for _ in range(e):
    a, b, c = map(int,input().split())
    graph[a].append((b,c))
    distance[a][b] = c
    # 가능한 경로 heap 에 넣어주기 
    heapq.heappush(q, (c,a,b))
    
while q :
    dist, a, b = heapq.heappop(q)
    # 출발지와 도착지가 같다면 사이클 발생 
    if a == b :
        print(dist)
        break
    
    # 이미 처리 됐다면 넘어감 
    if distance[a][b] < dist:
        continue

    # g에서 갈 수 있는 경로 
    for i in graph[b]:  
        cost = dist + i[1]
        
        # s -> g -> i[0] 보다 s -> i[0]이 빠르면 갱신 
        if cost < distance[a][i[0]] :
            distance[a][i[0]] = cost 
            heapq.heappush(q, (cost, a, i[0]))

else:
    print(-1)