다익스트라 알고리즘 조금 어려운 문제로 오랜만에 재활하기1

1. 문제

 

20007번: 떡 돌리기 (acmicpc.net)

20007번: 떡 돌리기

 

2. 풀이

 

다익스트라는 기본 구현 그대로.. 하면 되는데..

 

문제 조건을 올바르게 생각해야한다

 

1) "하루에 x보다 먼 거리를 걷지 않고, 거리가 가까운 집부터 방문한다"

 

거리가 가까운 집부터 방문한다고 하니까, 

 

그래서 다익스트라로 얻은 최단거리 배열을 오름차순으로 정렬해줘서, 작은 거리부터 방문해줘야한다.

 

2) "잠은 꼭 본인 집에서 자야하므로 왕복할 수 없는 거리는 다음날 가기로 다짐한다"

 

y에서 다른 집 i까지 최단 거리가 d이면, 2d가 현재 이동할 수 있는 거리보다 크다면, 이동을 못한다는 뜻이죠

 

3) "떡은 한번에 하나씩만 들고 갈 수 있다"

 

y에서 다른 집 i까지 이동하고, 다른 집 j까지 이동할 수 없고,

 

무조건 y에서 다른 집 i로 간 다음, 다시 y로 와서, y에서 j로 가야하는, 왕복을 해줘야한다.

 

4) "집들 사이에는 m개의 양방향 도로가 있다" 

 

y에서 다른 집 i까지 최단 거리가 d이면, 양방향이기 때문에, 되돌아오는 최단 거리도 d이다.

 

-----------------------------------------------------------------------------------------------------------------------------------

 

y번에서 출발한 다익스트라 배열 dist에서, 오름차순으로 정렬하면...

 

처음에 집 번호도 같이 알고 있어야 헀나 생각했는데... 생각해보니까 그건 전혀 필요가 없네

 

왜냐

 

dist에 존재하는 값들은 무조건 0이상인데, 0은 오직 자기 자신인 y번에만 해당하므로,

 

dist를 오름차순 정렬하고, 1번부터 순회해서 현 시점의 누적 거리가 x이하라면, 계속 왕복거리 2d를 누적해주고

 

x보다 커진다면... 누적 거리를 초기화하며, 일수를 1 더해준다.

 

하나 더 주의할 점은..

 

왕복 거리 2d가 그냥 x보다 클 수 있다는 점이다.. 이러면 모든 집을 방문할 수가 없다

 

모든 집을 방문할 수 없는 경우가, 1) 애초에 최단 경로가 존재하지 않아 INF인 경우,

 

그 다음, 2) 그냥 2d가 x보다 커버린 경우

 

import heapq
from sys import stdin

INF = 100000000000000000000000000

def dijkstra(start):

    distance = [INF]*(n)

    q = []

    heapq.heappush(q,(0,start))
    
    distance[start] = 0

    while q:
        
        dist,u = heapq.heappop(q)

        if distance[u] < dist:
            
            continue
        
        for b,c in graph[u]:
            
            cost = dist + c

            if distance[b] > cost:
                
                distance[b] = cost

                heapq.heappush(q,(cost,b))
    
    return distance

n,m,x,y = map(int,stdin.readline().split())

graph = [[] for _ in range(n)]

for _ in range(m):

    a,b,c = map(int,stdin.readline().split())

    graph[a].append((b,c))
    graph[b].append((a,c))

dist = dijkstra(y)

dist.sort()

arrive = True

sum_dist = 0

answer = 1

for d in dist[1:]:

    if sum_dist+2*d <= x:
        
        sum_dist += 2*d
    
    else:
        
        if 2*d > x:
            
            arrive = False
            break

        sum_dist = 2*d
        answer += 1


if arrive == False:
    
    print(-1)

else:
    
    print(answer)