Overview

In a city where passing through flooded points incurs an additional cost \(T\), we find the “shortest time” from point \(1\) to point \(N\). By treating each movement as “road travel time + \(T\) if the destination point is flooded,” this reduces to a standard shortest path problem.

Analysis

Key Insight

• The additional time loss \(T\) occurs “when passing through a flooded point.”
• Since a route can be thought of as “a sequence of points,” we can organize it as: for each movement, if the next destination point is flooded, add \(T\) at that point.
• Starting point \(1\) is no exception — if it is flooded, \(T\) is incurred from the very beginning (reflected in the initial distance in the code).

In other words, the cost of traversing edge \((u \to v)\) is: - \(w(u,v) + (T\ \text{if}\ v\ \text{is flooded, else}\ 0)\)

Since all costs are non-negative, Dijkstra’s algorithm can be used.

Why a Naive Approach Fails

• Enumerating all paths and taking the minimum is impossible because the number of paths grows exponentially.
• BFS cannot guarantee shortest paths because edge weights are not uniform (\(w_i\) varies, and \(T\) may also be added).
• Since \(N, M \le 2\times 10^5\), we need to solve the shortest path in \(O((N+M)\log N)\) time.

How to Solve It

• Consider new weights formed by adding the “flooding penalty of the destination point” to the “road weight,” and solve it as a standard shortest path problem using Dijkstra’s algorithm.

Algorithm

1. Build the graph using an adjacency list (each road is bidirectional).
2. Store flooded points as a boolean array flooded[v].
3. Run Dijkstra’s algorithm.
   • Initial value: dist[1] = (T if point 1 is flooded, else 0)
   • Extract (current distance, vertex) from the priority queue.
   • For edge \((u, v, w)\), compute the candidate distance as $\( nd = dist[u] + w + (flooded[v] ? T : 0) \)$ and update accordingly.
4. dist[N] is the answer.

Concrete Example

For instance, if we travel \(1 \to 3\) and point \(3\) is flooded, then “\(T\) is added on top of road time \(w(1,3)\)” for that movement. Next, if we travel \(3 \to 5\) and point \(5\) is flooded, then another \(T\) is added for that movement. By thinking of it as “charged upon arrival,” we can simply compute the shortest path with addition.

Complexity

• Time complexity: \(O((N+M)\log N)\) (Dijkstra’s algorithm + priority queue)
• Space complexity: \(O(N+M)\) (adjacency list, distance array, flooded array, etc.)

Implementation Notes

• Add the flooding penalty to the “destination point”: Writing nd = d + w + (T if flooded[v] else 0) is natural and less prone to counting errors.

• Handling the starting point: If point \(1\) is flooded, \(T\) is also incurred, so set dist[1] to \(T\) from the start.

• Validity check for values extracted from the heap: Including if d != dist[u]: continue prevents exploration based on outdated information.

• Since the input is large, sys.stdin.buffer.read() is used for fast reading.

• Distances can become very large, so use a sufficiently large value like INF = 10**30.

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0

    N, M, K, T = data[idx], data[idx + 1], data[idx + 2], data[idx + 3]
    idx += 4

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = data[idx], data[idx + 1], data[idx + 2]
        idx += 3
        adj[u].append((v, w))
        adj[v].append((u, w))

    flooded = [False] * (N + 1)
    for _ in range(K):
        g = data[idx]
        idx += 1
        flooded[g] = True

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = T if flooded[1] else 0

    hq = [(dist[1], 1)]
    while hq:
        d, u = heapq.heappop(hq)
        if d != dist[u]:
            continue
        if u == N:
            break
        for v, w in adj[u]:
            nd = d + w + (T if flooded[v] else 0)
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))

    print(dist[N])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.