[백준] 1504번 특정한 최단 경로

어느 정점을 들르는 경우는 전부 플로이드-워셜로 푸는 줄 알았다.. 그러나 플로이드-워셜은 기본적으로 O(N^3)의 시간 복잡도를 갖기 때문에 간선이나 정점이 500개 이상인 문제에서는 거의 다 시간초과로 걸려버린다.

<플로이드워셜 코드, 시간초과>

INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0
#print(graph)
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

d1, d2 = map(int, input().split())
distance = min(graph[1][d1] + graph[d1][d2] + graph[d2][n], graph[1][d2] + graph[d2][d1] + graph[d1][n])
if distance > INF:
    print(-1)
else:
    print(distance)

그렇다면 그냥 다익스트라로 푸는 수 밖에...

<다익스트라 알고리즘 코드, 통과>

import heapq
import sys
input = sys.stdin.readline
INF = 0xFFFFFF
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

d1, d2 = map(int, input().split())

def dijkstra(start, end):
    distance = [INF] * (n+1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, dist = heapq.heappop(q)
        if distance[dist] < cost:
            continue
        for d, c in graph[dist]:
            tmp = c + cost
            if distance[d] > tmp:
                distance[d] = tmp
                heapq.heappush(q, (tmp, d))
    return distance[end]

s1 = dijkstra(1, d1) + dijkstra(d1, d2) + dijkstra(d2, n)
s2 = dijkstra(1, d2) + dijkstra(d2, d1) + dijkstra(d1, n)
if s1 >= INF and s2 >= INF:
    print(-1)
else:
    print(min(s1, s2))

자꾸 중간중간에 에러가 떠서 고치느라 화남.. 

오버플로우가 날 걱정도 해야하고... 100퍼센트에서 틀릴 때에는 overflow를 의심하거나, 부등호를 의심해야한다.

 

나는 마지막에 있는 if-else문에서 > INF로 했다가 100퍼센트에서 틀렸다. >=INF 로 해야함.

사소한 것들 놓치지 말 것.