문제

군인인 성현이는 전역 후에 새 집으로 이사를 갔다. 주변 이웃과 친하게 지내고 싶은 마음에 이웃집에 떡을 돌리기로 했다. 떡은 한번에 하나씩만 들고 갈 수 있다. 집들 사이에는 총 M개의 양방향 도로가 있다. 귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다. 또 잠은 꼭 본인 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로 다짐한다. N-1개의 이웃집 모두에게 떡을 돌리기 위해서는 최소 며칠이 소요될 것인가.

집의 번호는 0번부터 N-1번까지 차례대로 붙어있다.

# 20007
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

import heapq
n, m, x, y = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
    
def dijkstra(start):
    q = []
    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]))
                
dijkstra(y)
day = 1
today_len = 0

distance.sort()

for i in range(1, n):
    if distance[i] * 2 > x:
        day = -1
        break
    if today_len + distance[i] * 2 > x:
        day += 1
        today_len = distance[i] * 2
    else:
        today_len += distance[i] * 2
        
print(day)

백준 20007 떡 돌리기