boj 1504 : 특정한 최단경로

문제 주소: https://www.acmicpc.net/problem/1504

난이도: gold 4

1.문제설명

• 무향그래프(중요)에서 1번정점에서 N번정점으로 이동하려한다.
• 하지만 이때 꼭 지나야하는 두 정점이 있다.
• 한번 방문한 정점도 방문가능하고, 한번 이용한 간선도 방문 가능하지만 최단경로로 이동해야한다.
• 두어진 주 정점을 거쳐 N번정점까지 최단경로로 이동할때 그 거리를 출력해라(이동 불가능하면 -1)

2.문제해결 아이디어.

• 다익스트라 문제이며 케이스를 2개로 나눌수 있다.
  • 1 -> v1 -> v2 -> N
  • 1 -> v2 -> v1 -> N
• 두가지 케이스를 비교하면 된다.

3.문제접근법

• 무향그래프일 경우 그래프 세팅

for i in range(E):
    a,b,cost = map(int,input().split())
    graph[a].append((b,cost))
    graph[b].append((a,cost))

• 케이스 비교 후 출력

case1 = dijkstra(1)[v1] + dijkstra(v1)[v2]+ dijkstra(v2)[V]
case2 = dijkstra(1)[v2] + dijkstra(v2)[v1]+ dijkstra(v1)[V]

if case1 >= INF and case2 >= INF:
    print(-1)
else:
    print(min(case1, case2))

4.특별히 참고할 사항

• 최근 풀이한 두 문제 모두 다익스트라에서 distance 리스트를 return받아서 문제를 해결한다.
• 무향그래프인지 유향그래프인지 주의해서 보자
• 필자도 안읽고 무지성으로 시도하다 틀려서 보니 무향그래프였다.

5.코드구현

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

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


for i in range(E):
    a,b,cost = map(int,input().split())
    graph[a].append((b,cost))
    graph[b].append((a,cost))

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

def dijkstra(start):
    q = []
    distance = [INF] * (V + 1)
    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

case1 = dijkstra(1)[v1] + dijkstra(v1)[v2]+ dijkstra(v2)[V]
case2 = dijkstra(1)[v2] + dijkstra(v2)[v1]+ dijkstra(v1)[V]

if case1 >= INF and case2 >= INF:
    print(-1)
else:
    print(min(case1, case2))