[백준] 드디어 실버에서 골드로

 

짜쟌 하루에 평균 한 문제씩 2달간 풀면 브론즈에서 골드로 넘어갈 수 있는 것 같다.

 

 

마지막 문제는 특정 지점을 경유해서 1번에서 n번 노드로 가는 최단 경로를 구하는 문제였다.

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

1504번: 특정한 최단 경로

 

내가 푼 풀이

# BOJ_1504
# 1. (1, v1) + (v1, v2) + (v2, n)
# 2. (1, v2) + (v2, v1) + (v1, n)
# 1과 2중 최솟값
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)


# 입력
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))
    graph[b].append((a, c))
# 경유해야 하는 정점
v1, v2 = map(int, input().split())


# 다익스트라 최단 경로 알고리즘
def dijkstra(start):
    distance = [INF] * (n + 1)
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    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


# 최단경로가 무한대로 가면 -1 출력하고 코드 종료
def check_infinite(dist1, dist2):
    if dist1 == INF or dist2 == INF:
        print(-1)
        sys.exit()


distance = dijkstra(1)
zero_to_v1 = distance[v1]
zero_to_v2 = distance[v2]
check_infinite(zero_to_v1, zero_to_v2)

distance = dijkstra(v1)
v1_to_v2 = distance[v2]
v1_to_n = distance[n]
check_infinite(v1_to_v2, v1_to_n)
distance = dijkstra(v2)
v2_to_v1 = distance[v1]
v2_to_n = distance[n]
check_infinite(v2_to_v1, v2_to_n)

zero_v1_v2_n = zero_to_v1 + v1_to_v2 + v2_to_n
zero_v2_v1_n = zero_to_v2 + v2_to_v1 + v1_to_n
check_infinite(zero_v1_v2_n, zero_v2_v1_n)
print(min(zero_v1_v2_n, zero_v2_v1_n))

 

 

가독성이 더 좋은 다른 사람 풀이

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

v, e = map(int, input().split())
graph = [[] for _ in range(v + 1)]

# 방향성 없는 그래프이므로 x, y일 때와 y, x일 때 모두 추가
for _ in range(e):
    x, y, cost = map(int, input().split())
    graph[x].append((y, cost))
    graph[y].append((x, cost))
    
    
def dijkstra(start):
    distance = [INF] * (v + 1)
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]

            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    # 반환값은 최단 거리 배열
    return distance


v1, v2 = map(int, input().split())

# 출발점이 각각 1, v1, v2일 때의 최단 거리 배열
original_distance = dijkstra(1)
v1_distance = dijkstra(v1)
v2_distance = dijkstra(v2)

v1_path = original_distance[v1] + v1_distance[v2] + v2_distance[v]
v2_path = original_distance[v2] + v2_distance[v1] + v1_distance[v]

result = min(v1_path, v2_path)
print(result if result < INF else -1)