以下では \(M\) 本の道路 \((u,v)\) について、\(N\) 頂点のグラフにおいて、頂点 \(u\) から頂点 \(v\) への有向辺と \(v\) から \(u\) への有向辺がそれぞれ存在すると考えます。

頂点 \(u\) から頂点 \(v\) へのがあるとき、交差点 \(v\) の混雑度が \(K\) 以上のときはこの辺の重みを \(2\) 、そうでない場合は \(1\) として頂点 \(1\) から 頂点 \(N\) までの最短距離を求め、最後に交差点 \(N\) の混雑度が \(K\) 以上の場合にその最短距離から \(1\) 引くと、この問題の答えになります。

最初に求める頂点 \(1\) から 頂点 \(N\) までの最短距離では、 経路上の頂点の列 \((v_0,v_1,\ldots,v_L)\) のうち \(v_1,v_2,\ldots,v_L\) で交差点の混雑度が \(K\) 以上の頂点数分追加でかかっていることになっている。今回、\(v_L=N\) の場合を考えており、最後の交差点 \(N\) の混雑度は考えないので、そこで頂点 \(N\) の混雑度が \(K\) 以上の場合は最後に \(1\) を引くという操作を入れる必要がある。

最短距離はダイクストラ法で求めることで時間計算量 \(\mathrm{O}((N+M)\log N)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> dist(n, 1e9);
    vector<vector<int>> g(n);
    vector<int> deg(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        deg[u]++, deg[v]++;

        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.emplace(0, 0);
    dist[0] = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (dist[u] != d) continue;
        for (auto v : g[u]) {
            int nd = d + 1;
            if (deg[v] >= k) nd++;
            if (dist[v] > nd) dist[v] = nd, pq.emplace(nd, v);
        }
    }
    if (dist[n - 1] == (int)1e9) {
        cout << -1 << endl;
        return 0;
    }
    if (deg[n - 1] >= k) dist[n - 1]--;
    cout << dist[n - 1];
}