국왕의 방문[백준 2982]

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

 

문제 조건을 잘 살펴 봐야 하는데 이미 도로에 들어갔을 때 국왕이 사용하는 도로이면 상관없이 사용이 가능하다는 것을 알아야 한다. 

import sys
import heapq
from collections import defaultdict

def parse_input():
    data = sys.stdin.read().splitlines()
    N, M = map(int, data[0].split())
    A, B, K, G = map(int, data[1].split())
    g_path = list(map(int, data[2].split()))

    graph = defaultdict(list)
    idx = 3
    for _ in range(M):
        U, V, L = map(int, data[idx].split())
        graph[U].append((V, L))
        graph[V].append((U, L))
        idx += 1

    return N, M, A, B, K, G, g_path, graph

def calculate_road_block_times(g_path, start_time, graph):

    road_block = defaultdict(list)
    current_time = start_time
    # g_path = [교차로1, 교차로2, 교차로3, ...] 순서

    for i in range(len(g_path) - 1):
        U, V = g_path[i], g_path[i + 1]
        # U->V 이동 시간 찾기
        travel_time = None
        for nxt, t in graph[U]:
            if nxt == V:
                travel_time = t
                break

        if travel_time is not None:
            # U->V 구간이 current_time~(current_time+travel_time) 동안 점유
            road_block[(U, V)].append((current_time, current_time + travel_time))
            road_block[(V, U)].append((current_time, current_time + travel_time))
            current_time += travel_time

    return road_block

def dijkstra_with_blocking(graph, road_block, start, end, start_delay):

    dist = {}
    for node in graph:
        dist[node] = float('inf')

    dist[start] = start_delay  # 상근이는 K분에 start 교차로를 출발(도착한 것과 동일 시)
    pq = []
    heapq.heappush(pq, (start_delay, start))  # (도착시각, 노드)

    while pq:
        current_time, current_node = heapq.heappop(pq)
        if current_time > dist[current_node]:
            continue
        if current_node == end:
            # 이미 end 최소값을 구했으면 여기서 종료 가능
            return current_time-start_delay

        for neighbor, travel_time in graph[current_node]:
            enter_time = current_time  # 지금 교차로에 '도착'한 시각 = 곧 도로에 '진입'하는 시점
            if (current_node, neighbor) in road_block:
                # 여러 구간이 있을 수 있으므로 확인
                for (block_start, block_end) in road_block[(current_node, neighbor)]:
                    # "새로 진입" 시점 enter_time이 [block_start, block_end) 에 걸친다면 대기
                    if block_start <= enter_time < block_end:
                        enter_time = block_end  # 대기 후 block_end 시각에 진입
                        break

            # 통과 완료 시각 = 진입시각 + travel_time
            next_time = enter_time + travel_time

            # dist[neighbor] 갱신
            if next_time < dist[neighbor]:
                dist[neighbor] = next_time
                heapq.heappush(pq, (next_time, neighbor))

    return dist[end]-start_delay

def main():
    # 입력 받기
    N, M, A, B, K, G, g_path, graph = parse_input()
    road_block = calculate_road_block_times(g_path, 0, graph)

    # 다익스트라 계산
    answer = dijkstra_with_blocking(graph, road_block, A, B, K)
    print(answer)

if __name__=="__main__":
    main()