https://www.acmicpc.net/problem/20007
시간 1초, 메모리 512MB
input :
- N, M, X, Y (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N)
- A B C(0 ≤ A,B < N, 1 ≤ C ≤ 10,000)
output :
- 성현이의 집을 Y 라고 할 때, 이웃집 모두에 떡을 돌리기 위한 최소 일을 출력
- 모두 방문할수 없으면 -1을 출력
조건 :
- 떡은 한번에 하나씩만 들고 갈 수 있다.
- 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문(다익스트라 필요)
- 잠은 꼭 본인 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로 다짐
일단 성현이의 집을 기준으로 최단 거리들을 잡아야 한다.
그래서 다익스트라를 이용하자.
오랜만에 쓰려고 하니까 좀 기억이 안 나기도 했다.
다시 한 번 상기하도록 하자.
다익스트라의 경우 시작하는 지점의 거리를 0으로 초기화를 하며 이 지점을 q에 heapq로 넣어준다.
우선순위 큐를 사용해서 가장 짧은 거리부터 이동하도록 한다.
그리고, 다른 그래프 들과 다르게 다음 노드까지 이동을 했을 때의 거리가 dp 값에 있는 값보다 작은 경우에만 q에 append 하여 준다.
dp = [float('inf')] * n
q = []
heappush(q, (0, y))
dp[y] = 0
while q:
dis, now_node = heappop(q)
if dp[now_node] < dis:
continue
for next_node, next_cost in graph[now_node]:
cost = next_cost + dis
if dp[next_node] > cost:
dp[next_node] = cost
heappush(q, (cost, next_node))그리고 이 최단 거리가 x보다 큰 경우에는 어떤 짓거리를 해도 성현이가 떡을 돌리지 않으니까 이 경우를 -1ㄹ을 출력하고 exit()를 하자.
그렇기에 왕복의 경우를 다 따져야 해서 거리에 대한 값에 2를 곱해준다.
그리고 날짜를 샐때는 현재까지 이동 거리 + 다음 거리 > x 이면 날짜를 하루 올리고, 현재까지 이동 거리를 다시 0으로 초기화 시키자.
for i in range(len(dp)):
dp[i] *= 2
dp.sort()
if max(dp) > x:
print(-1)
exit()
now, ans = 0, 1
for item in dp:
if now + item > x:
ans += 1
now = 0
now += item
print(ans)import sys
from heapq import heappop, heappush
n, m, x, y = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n)]
for i in range(m):
a, b, c = map(int, sys.stdin.readline().split())
graph[a].append((b, c))
graph[b].append((a, c))
dp = [float('inf')] * n
q = []
heappush(q, (0, y))
dp[y] = 0
while q:
dis, now_node = heappop(q)
if dp[now_node] < dis:
continue
for next_node, next_cost in graph[now_node]:
cost = next_cost + dis
if dp[next_node] > cost:
dp[next_node] = cost
heappush(q, (cost, next_node))
for i in range(len(dp)):
dp[i] *= 2
dp.sort()
if max(dp) > x:
print(-1)
exit()
now, ans = 0, 1
for item in dp:
if now + item > x:
ans += 1
now = 0
now += item
print(ans)
