Overview

This problem asks us to find the shortest path in a weighted undirected graph under the condition that an additional cost is incurred when passing through certain vertices.

Analysis

This problem is fundamentally a shortest path problem, but there are several important points to consider.

First, when you stop at a flooded location, an additional time loss of \(T\) is incurred at that moment. This is not an “edge weight” but rather a cost that occurs “the instant you reach a vertex.” In other words, when managing shortest distances with Dijkstra’s algorithm, we need to consider not just the edge costs but also whether the destination vertex is flooded.

Additionally, note that if the starting point (vertex \(1\)) or the destination (vertex \(N\)) is flooded, a time loss also occurs. In particular, if the starting point is already flooded, \(T\) must be added as the initial cost.

Naive methods (such as brute-force search or DFS) cannot solve this within a reasonable time limit since the number of vertices \(N\) can be up to \(2 \times 10^5\). Therefore, we use Dijkstra’s algorithm, an efficient algorithm for finding shortest paths.

Dijkstra’s algorithm uses a priority queue (heap) to process vertices in order of lowest cost, efficiently computing the shortest distance to each vertex.

Algorithm

In this problem, we extend Dijkstra’s algorithm as follows:

1. Graph Construction

   • Store each road as a bidirectional edge in the adjacency list adj. Each edge is stored in the form (adjacent vertex, edge weight).

2. Flooded Location Management

   • Manage flooded vertices using a set flooded, enabling fast lookup of whether a vertex is flooded.

3. Dijkstra’s Algorithm Initialization

   • Prepare an array dist to record the shortest distance from vertex \(1\) to each vertex, initialized to \(\infty\).
   • If vertex \(1\) is flooded, the initial cost is \(T\); otherwise, it is \(0\).
   • Add the initial state to the priority queue in the form (cost, vertex number).

4. Dijkstra’s Algorithm Main Loop

   • Extract the vertex with the lowest cost from the queue. If its cost is greater than the current shortest distance, skip it.
   • If the vertex is the destination \(N\), the cost at that point is the answer, so output it and terminate.
   • Otherwise, compute the new cost for each adjacent vertex:
     • The travel cost is current cost + edge weight + (T if the destination is flooded)
     • If this new cost is less than the existing shortest distance, update it and add it to the queue.

In this way, we can find the shortest path while accounting for additional costs at each vertex.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • This is the standard complexity of Dijkstra’s algorithm. Each edge is processed at most once, and each priority queue operation costs \(\log N\).
• Space complexity: \(O(N + M)\)
  • Memory used for the adjacency list, distance array, set of flooded locations, etc.

Implementation Notes

• Use a set for flooded location lookup to achieve \(O(1)\) per query.

• In Dijkstra’s algorithm, the same vertex may be added to the queue with different costs, so it is essential to skip a vertex if the extracted cost is greater than its current shortest distance.

• Do not forget to handle the case where the starting point or destination is flooded.

  Source Code

import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    flooded = set()
    if K > 0:
        for _ in range(K):
            g = int(data[idx]); idx += 1
            flooded.add(g)
    
    # ダイクストラ法
    # 頂点番号、コスト
    dist = [float('inf')] * (N+1)
    dist[1] = T if 1 in flooded else 0
    pq = [(dist[1], 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N:
            print(d)
            return
        for v, w in adj[u]:
            cost_add = w + (T if v in flooded else 0)
            new_dist = d + cost_add
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.