Shopping Mall

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n, m, k; cin >> n >> m >> k;
    10    vector<int> v(n + 1);
    11    for (int i = 1; i <= n; i++) cin >> v[i];
    12    vector<vector<int>> adj(n + 1);
    13    for (int i = 0; i < m; i++) {
    14        int u, v; cin >> u >> v;
    15        adj[u].push_back(v);
    16        adj[v].push_back(u);
    17    }
    18    vector<vector<int>> dist(k + 1, vector<int>(n + 1, inf)); //dist[i][j] = the minimum cost to reach node j with the first i items purchased
    19    deque<pair<int, int>> q;
    20    for (int i = 1; i <= n; i++) {
    21        if (v[i] == 0) {
    22            dist[0][i] = 0;
    23            q.push_back(make_pair(i, 0));
    24        }
    25    }
    26    while (!q.empty()) {
    27        auto[u, p] = q.front(); q.pop_front();
    28        int cur = dist[p][u];
    29        if (p < k && v[u] == p + 1) {
    30           if (cur < dist[p + 1][u]) {
    31            dist[p + 1][u] = cur;
    32            q.push_front(make_pair(u, p + 1));
    33           }
    34        }
    35        for (int v : adj[u]) {
    36            if (dist[p][v] > cur + 1) {
    37                dist[p][v] = cur + 1;
    38                q.push_back(make_pair(v, p));
    39            }
    40        }
    41    }
    42    int ans = inf;
    43    for (int i = 1; i <= n; i++) {
    44        ans = min(ans, dist[k][i]);
    45    }
    46    cout << ans << '\n';
    47    return 0;
    48}