この問題は、雲と現在のもこもこ度の組を頂点としたグラフの最短経路問題と考えることができます。

より具体的には、次のようなグラフを考えます。

\(\bigl(\)雲 \(i,\) 現在のもこもこ度 \(f\bigr)\ (1\le i\le N,1\le f\le5)\) を頂点とし、次のような辺をもつグラフ

• \((U _ j,f)\) と \((V _ j,f)\) を相互に結ぶコスト \(T _ jf\) の辺 \((1\le j\le M,1\le f\le5)\)
• \((i,f)\) から \((i,F _ i)\) へコスト \(0\) の辺 \((1\le i\le N,1\le f\le 5)\)

このグラフにおいて、\((1,F _ 1)\) から \((N,F _ N)\) の最短経路の長さが求めるものです。

あとは、Dijkstra 法などを用いてこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> F(N);
    for (int& f : F) {
        cin >> f;
        --f;
    }

    // (雲, ふわふわ度) を頂点にもつグラフを作る
    vector edges(N, vector<vector<tuple<int, int, long>>>(5));
    for (int i = 0; i < N; ++i) {
        for (int f = 0; f < 5; ++f) {
            edges[i][f].emplace_back(i, F[i], 0); // 現在いる雲のふわふわ度を採用する
        }
    }

    for (int i = 0; i < M; ++i) {
        int u, v, t;
        cin >> u >> v >> t;
        --u;
        --v;
        // それぞれのふわふわ度に対して辺を張る
        for (int f = 0; f < 5; ++f) {
            edges[u][f].emplace_back(v, f, t * static_cast<long>(f + 1));
            edges[v][f].emplace_back(u, f, t * static_cast<long>(f + 1));
        }
    }

    // Dijkstra 法で最短距離を求める
    vector distance(N, vector<long>(5, 1000000000000000000));
    priority_queue<tuple<long, int, int>, vector<tuple<long, int, int>>, greater<tuple<long, int, int>>> pq;
    pq.emplace(distance[0][F[0]] = 0, 0, F[0]); // (0, F[0]) からスタートする
    while (!pq.empty()) {
        auto [dist, now, fluffiness] = pq.top();
        pq.pop();
        if (now == N - 1) { // 雲 N に到着したら
            cout << dist << endl; // それが最短経路
            return 0;
        }
        for (auto [next, next_fluffiness, cost] : edges[now][fluffiness]) {
            if (distance[next][next_fluffiness] > dist + cost) {
                pq.emplace(distance[next][next_fluffiness] = dist + cost, next, next_fluffiness);
            }
        }
    }
    // 到着できなければ -1
    cout << -1 << endl;
    return 0;
}

from heapq import heappush, heappop


N, M, K = map(int, input().split())
F = [f - 1 for f in map(int, input().split())]

# (雲, ふわふわ度) を頂点にもつグラフを作る
edges = [[[] for _ in range(5)] for _ in range(N)]
for i in range(N):
    for f in range(5):
        edges[i][f].append((i, F[i], 0)) # 現在いる雲のふわふわ度を採用する

for i in range(M):
    u, v, t = map(int, input().split())
    u -= 1
    v -= 1
    # それぞれのふわふわ度に対して辺を張る
    for f in range(5):
        edges[u][f].append((v, f, t * (f + 1)))
        edges[v][f].append((u, f, t * (f + 1)))

# Dijkstra 法で最短距離を求める
distance = [[10 ** 18 for _ in range(5)] for _ in range(N)]
distance[0][F[0]] = 0
heap = []
heappush(heap, (0, 0, F[0])) # (0, F[0]) からスタートする

while len(heap) > 0:
    dist, now, fluffiness = heappop(heap)
    if now == N - 1: # 雲 N に到達したら
        print(dist) # それが最短経路
        break

    for next, next_fluffiness, cost in edges[now][fluffiness]:
        if distance[next][next_fluffiness] > dist + cost:
            distance[next][next_fluffiness] = dist + cost
            heappush(heap, (dist + cost, next, next_fluffiness))
else: # 到着できなければ -1
    print(-1)