문제

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

풀이

정점 사이에 간선은 양방향으로 이동할 수 있다. 값을 입력받을 때 양방향으로 이동할 수 있는 간선이라는 점을 반영해서 양쪽 노드 모두에 간선 정보를 append한다.

(위에 입력예시 그린거)
1번 정점에서 출발해서 > 목적지 N까지 가는 방법은
1. 1번에서 출발 > v1 > v2 > N
2. 1번에서 출발 > v2 > v1 > N
이렇게 두가지이다. 두가지 경우를 구하고 더 작은 값이 최단경로임 ~

각 정점에서 출발해서 다른 정점까지의 최단경로는 다익스트라 알고리즘으로 구했다.

코드

import sys 
import heapq 

node,edge=map(int,input().split())
graph=[[] for _ in range(node+1)]
for _ in range(edge):
    a,b,c=map(int,sys.stdin.readline().strip().split())
    # 양방향 그래프
    graph[a].append([b,c])
    graph[b].append([a,c])
    
v1,v2=map(int,input().split())

INF=int(1e9)
def dijkstra(start):
    distance=[INF]*(node+1)
    distance[start]=0
    q=[]
    heapq.heappush(q,[0,start])
    while q:
        dist,n=heapq.heappop(q)
        for i in graph[n]:
            cost=i[1]+dist
            if cost<distance[i[0]]:
            	distance[i[0]]=cost
                heapq.heappush(q,[cost,i[0]])
    return distance 


d_start_1=dijkstra(1)
from_one_to_v1=d_start_1[v1] # 출발점 1에서 v1까지
from_one_to_v2=d_start_1[v2] # 출발점 1에서 v2까지

d_start_v1=dijkstra(v1)
from_v1_to_v2=d_start_v1[v2] # v1에서 v2까지
from_v1_to_n=d_start_v1[node] # v1에서 목적지 n까지

d_start_v2=dijkstra(v2)
from_v2_to_v1=d_start_v2[v1] # v2에서 v1까지 
from_v2_to_n=d_start_v2[node] # v2에서 목적지 n까지

# 출발점 1 -> v1 경유 -> v2 경유 -> 목적지 n
d1=from_one_to_v1+from_v1_to_v2+from_v2_to_n
# 출발점 1 -> v2 경유 -> v1 경유 -> 목적지 n
d2=from_one_to_v2+from_v2_to_v1+from_v1_to_n

# 두 개의 경로 중 더 가까운 거리를 답으로 채택한다. 
ans=min(d1,d2)
if ans>=INF: # 갈 수 있는 방법이 없으면 -1 출력
    print(-1)
else:
    print(ans)
    

(●'◡'●)(/ω＼)(^///^)
인턴하면서 코테 엄청푸는중 ,,,,,,,,,,,,,,