내 인생 이대로 ㅈ될 수 없다

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

내 풀이

import sys
import heapq

INF = int(1e9)
input = sys.stdin.readline
def solution():
    N,E = map(int,input().split())
    graph = [[] for _ in range(N+1)]

    for _ in range(E):
        a,b,c = map(int,input().split())
        graph[a].append((b,c))
        graph[b].append((a,c))
    
    def ekdlrtmxmfk(start):
        distance = [INF] * (N+1)
        distance[start]=0
        q=[]
        heapq.heappush(q,(0,start))
        while q:
            dist,now = heapq.heappop(q)
            if distance[now] < dist:
                continue
            for i in graph[now]:
                cost = i[1] + dist
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q,(cost,i[0]))
        return distance
    
    
    x,y = map(int,input().split())

    original = ekdlrtmxmfk(1)
    #print(original)
    p1=ekdlrtmxmfk(x)
    #print(p1)
    p2=ekdlrtmxmfk(y)
    #print(p2)
    p1_path = original[x] + p1[y] + p2[N]
    p2_path = original[y] + p2[x] + p1[N]

    #print(p1_path,p2_path)
    answer = min(p1_path,p2_path)

    print(answer if answer <INF else -1)


solution()

최초에 문제 이해가 안됐다. 특정 노드를 반드시 거쳐가야한다는게 무슨말이지?

어차피 특정 노드를 거쳐가야하지않나?

잘 생각해보니

주어진 노드가 a,b,c,d 이고 특정 노드가 b,c라고하면

a -> d -> b- >c

혹은 

a -> c ->d ->b

이런식으로도 갈 수 있는데 이런 경우는 배제하고

무조건

a -> b -> c -> d 혹은

a -> c->b ->d 의 순서로 가라는 뜻이였다.

그러니까 최초 시작점 to 특정노드1 + 특정노드 1 to 특정노드 2 + 특정노드2 to 끝까지 or

               최초 시작점 to 특정노드2 + 특정노드 2 to 특정노드 1  + 특정노드1 to 끝까지 

중 최소 값을 택하면되는거다.  

다른사람의 풀이

import sys; input = sys.stdin.readline
from heapq import heappush, heappop

def dijkstra(start, end):
    dis = [0xffffff] * (N + 1)
    dis[start] = 0
    q = [[0, start]]
    while q:
        k, u = heappop(q)
        if k > dis[u]: continue
        for w, v in G[u]:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                heappush(q, [dis[v], v])

    return dis[end]

N, E = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append([w, v])
    G[v].append([w, u])

stop1, stop2 = map(int, input().split())

# 1 -> stop1 -> stop2 -> N
path1 = dijkstra(1, stop1) + dijkstra(stop1, stop2) + dijkstra(stop2, N)
# 1 -> stop2 -> stop1 -> N
path2 = dijkstra(1, stop2) + dijkstra(stop2, stop1) + dijkstra(stop1, N)

if path1 >= 0xffffff and path2 >= 0xffffff:
    print(-1)
else:
    print(min(path1, path2))