1. 문제 설명

떡 돌리기

2. 문제 분석

처음에는 한 번에 떡을 한 개만 들고 간다는 조건이 아니라 여러 개의 떡을 들고갈 수 있을 줄 알았기 때문에 note라는 배열에 특정 노드에 대한 경로를 기록해서 왕복 가능한 거리까지 카운트, 그 거리 안에서 추가로 이동 가능한 노드까지의 거리를 계산했다. 하지만 한 번에 한 개만 들고 갈 수 있기 때문에 보다 쉽게 하나씩 다익스트라로 얻은 거리 배열을 최소 거리 순서대로 정렬, 하나씩 계산하면 끝.

3. 나의 풀이

import sys
import heapq

INF = sys.maxsize

n, m, x, y = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c])
    nodes[b].append([a, c])

def Dijkstra():
    distances = [INF for _ in range(n)]
    distances[y] = 0
    pq = []
    heapq.heappush(pq, [0, y])

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        if distances[cur_node] < cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if distances[next_node] > cur_cost + next_cost:
                distances[next_node] = cur_cost + next_cost
                heapq.heappush(pq, [cur_cost + next_cost, next_node])
    return distances

distances = Dijkstra()
distances_idx = [[distance, idx] for idx, distance in enumerate(distances)]
distances_idx.sort()

if distances_idx[-1][0] * 2 > x: print(-1)
else:
    day = 1
    cur = 0
    for distance, idx in distances_idx:
        if cur + 2 * distance <= x:
            cur += 2 * distance
        else:
            day += 1
            cur = 2 * distance
    print(day)