Overview

By managing not only which cloud you are currently on, but also your “current fluffiness level” as part of the state, the problem reduces to a shortest path problem with non-negative edge weights.
The number of states is \(N \times K\), and since \(K \le 5\) is very small, the problem can be solved by running Dijkstra’s algorithm on the expanded state graph.

Analysis

The difficult aspect of this problem is that even on the same cloud, the cost of the next move changes depending on your current fluffiness level.

For example, suppose you are on cloud \(u\):

• If the current fluffiness level is \(1\), a path with base time \(10\) costs \(10 \times 1 = 10\)
• If the current fluffiness level is \(5\), the same path costs \(10 \times 5 = 50\)

In other words, knowing only that “we arrived at cloud \(u\) via the shortest path” is insufficient.
We need to know what fluffiness level we had when we arrived at cloud \(u\) in order to determine the optimal actions going forward.

Why a naive approach fails

The usual shortest path approach of maintaining a single distance value per vertex does not work.
This is because, even for the same cloud,

• It may be better to take a slightly longer detour to arrive with a smaller fluffiness level,
• Since the subsequent movement costs become cheaper, leading to a globally optimal solution.

Therefore, in this problem, we need to treat the combination of

• “Which cloud we are currently on”
• “What our current fluffiness level is”

as a single state.

How to construct the states

Define the state as \((u, f)\).

• \(u\) : the cloud we are currently on
• \(f\) : the current fluffiness level

The state transitions are of the following two types.

1. Adopt the cloud’s fluffiness level

When arriving at cloud \(u\), we can adopt that cloud’s fluffiness level \(F_u\).
Since this does not increase the time,

• There is a transition from \((u, f) \to (u, F_u)\) with cost \(0\).

2. Travel along a wind path

When the current fluffiness level is \(f\), and the base time of edge \((u, v)\) is \(t\), the movement cost is \(t \times f\).
Therefore,

• There is a transition from \((u, f) \to (v, f)\) with cost \(t \times f\).

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

Why this is sufficient

The fluffiness level is always between \(1\) and \(K\), and \(K \le 5\).
This means the number of states is at most around \(N \times 5\), which is perfectly manageable.

We start on cloud \(1\) with an initial fluffiness level of \(F_1\), so the starting state is

• \((1, F_1)\)

The goal is to “reach cloud \(N\)”, so the final fluffiness level does not matter, and the answer is

• \(\min_f \mathrm{dist}[N][f]\)

Algorithm

1. Define state \((u, f)\) as “being on cloud \(u\) with current fluffiness level \(f\)”.
2. Let dist[u][f] be the minimum time to reach that state.
3. The initial state is dist[1][F[1]] = 0.
4. Run Dijkstra’s algorithm using a priority queue.
5. When extracting state \((u, f)\), try the following:
   • Adoption transition: Add edge \((u, f) \to (u, F_u)\) with cost \(0\)
   • Movement transition: For each edge \((u, v, t)\), add edge \((u, f) \to (v, f)\) with cost \(t \times f\)
6. Finally, output min(dist[N][1:]). If unreachable, output -1.

Correspondence with the code

In the submitted code, the priority queue stores entries of the form

• (cost, node, current_fluff)

The following part corresponds to the “adopt the cloud’s fluffiness level” transition:

nf = F[u]
if nf != f and d < dist[u][nf]:
    dist[u][nf] = d
    heapq.heappush(pq, (d, u, nf))

Since the cost does not increase, this is exactly a cost \(0\) transition.

And the following part corresponds to the “travel along a wind path” transition:

for v, t in graph[u]:
    nd = d + t * f
    if nd < dist[v][f]:
        dist[v][f] = nd
        heapq.heappush(pq, (nd, v, f))

Complexity

• Time complexity: \(O((N K + M K)\log(NK))\)
• Space complexity: \(O(NK + M)\)

Since \(K \le 5\), this is effectively very lightweight and sufficiently fast.

Implementation notes

• Since the fluffiness level ranges from \(1\) to \(K\), it is convenient to make dist have K+1 columns and use 1-indexed access.

• In Dijkstra’s algorithm, values extracted from the priority queue may be outdated, so we skip them with:

  
  if d != dist[u][f]:
    continue
  

• The edge cost is \(T_j \times f\), and since \(T_j\) can be large, 64-bit integers are required in other languages. In Python, this is not an issue.

• Since the fluffiness level at the goal does not matter, the answer is the minimum value of dist[N][f].

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    F = [0] + [next(it) for _ in range(N)]

    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it)
        v = next(it)
        t = next(it)
        graph[u].append((v, t))
        graph[v].append((u, t))

    INF = 10**30
    dist = [[INF] * (K + 1) for _ in range(N + 1)]

    start_f = F[1]
    dist[1][start_f] = 0
    pq = [(0, 1, start_f)]  # (cost, node, current_fluff)

    while pq:
        d, u, f = heapq.heappop(pq)
        if d != dist[u][f]:
            continue

        # Optionally adopt the current cloud's fluffiness
        nf = F[u]
        if nf != f and d < dist[u][nf]:
            dist[u][nf] = d
            heapq.heappush(pq, (d, u, nf))

        # Move along edges keeping current fluffiness
        for v, t in graph[u]:
            nd = d + t * f
            if nd < dist[v][f]:
                dist[v][f] = nd
                heapq.heappush(pq, (nd, v, f))

    ans = min(dist[N][1:])
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.