특정한 최단 경로

❓문제

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

❗문제 정리

💡 다른 문제와 달리 지나가야하는 특정지점 g, h가 존재
시작지점 ->g->h->도착지점 / 시작지점 ->h->g->도착지점의 거리가 시작지점->도착지점의 거리와 같으면 시작지점에서 도착지점까지 갈 때, g->h 또는 h->g를 지난 것!!
💡양방향 간선이므로 도착지점의 인덱스에 (시작지점, 둘사이 거리) 넣어주기

• 다익스트라 알고리즘

📑코드

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

def heap_dijkstra(start):
    distance=[INF]*(n+1)
    
    q=[]

    heapq.heappush(q,(0,start))
    distance[start]=0

    while q:

        dist, now=heapq.heappop(q)
        if dist>distance[now]:
            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

n,e=map(int, input().split())
graph=[[] for _ in range(n+1)]
for i in range(e):
    a,b,c=map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

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

start_to=heap_dijkstra(1)#시작
u_to=heap_dijkstra(u)#u에서 시작
v_to=heap_dijkstra(v)#v에서 시작

if start_to[u]+u_to[v]+v_to[n]>=INF or start_to[v]+v_to[u]+u_to[n]>=INF:
    print(-1)
else:
    print(min(start_to[u]+u_to[v]+v_to[n],start_to[v]+v_to[u]+u_to[n]))

📝코드 설명

1. 필요한 라이브러리 임포트

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

2. 다익스트라 알고리즘

def heap_dijkstra(start):
    distance=[INF]*(n+1)
    
    q=[]
    heapq.heappush(q,(0,start))
    distance[start]=0

    while q:

        dist, now=heapq.heappop(q)
        if dist>distance[now]:
            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

큐를 이용한 다익스트라로 구현 (다익스트라 )

3. 인수 받아오기

n,e=map(int, input().split())
graph=[[] for _ in range(n+1)]
for i in range(e):
    a,b,c=map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

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

n(int) : 정점수, e(int) : 간선 수
a(int) : 시작지점, b(int) : 도착지점 c(int) :a와 b사이의 거리

• 양방향 간선이므로 도착지점의 인덱스에 (시작지점, 둘사이 거리) 넣어주기
  u,v(int) : 지나가야하는 곳

start_to=heap_dijkstra(1)#시작
u_to=heap_dijkstra(u)#u에서 시작
v_to=heap_dijkstra(v)#v에서 시작

start_to : 시작노드 1번부터 출발하여 최단거리 구하기
u_to : u부터 출발하여 최단거리 구하기
v_to : v부터 출발하여 최단거리 구하기

4. 출력하기

if start_to[u]+u_to[v]+v_to[n]>=INF or start_to[v]+v_to[u]+u_to[n]>=INF:
    print(-1)
else:
    print(min(start_to[u]+u_to[v]+v_to[n],start_to[v]+v_to[u]+u_to[n]))

시작지점 ->g->h->도착지점 / 시작지점 ->h->g->도착지점의 거리가 시작지점->도착지점의 거리와 같으면 시작지점에서 도착지점까지 갈 때, g->h 또는 h->g를 지난 것!!
계산한 거리가 INF보다 크거나 같은 경우 -1을 출력
아닌경우, 시작지점 ->g->h->도착지점 / 시작지점 ->h->g->도착지점의 거리 중 더 짧은 거리를 선택하여 출력

🎖제출 결과

💡insight

78%에서 오류 발생시, 출력 부분에서 값이 >=INF 일때로 설정하기.