この問題は、与えられたグラフをもとに別のグラフを構成し、そのグラフ上での最短距離を求めることで解くことができます（このような問題は俗に「拡張ダイクストラ」と呼ばれることがあります）。

\(2N\) 頂点 \(N+2M\) 辺の重み付き有向グラフであって、次のようなものを考えます（\(2N\) 個の頂点をそれぞれ頂点 \(1,\ldots,\) 頂点 \(2N\) と呼ぶこととします）。

• 与えられたグラフの辺 \((u,v)\) に対して、重み \(1\) の辺 \((u,v)\) および重み \(1\) の辺 \((v+N,u+N)\) が存在する。
• 重み \(X\) の辺 \((u,u+N)\) および重み \(X\) の辺 \((u+N,u)\) が存在する。
• 上記の辺以外は存在しない。

このグラフにおける頂点 \(1\) から頂点 \(N\) への最短距離と頂点 \(1\) から頂点 \(2N\) への最短距離のうち大きくないほうが答えとなります（頂点を \(1\) つ加え、頂点 \(N\) および \(2N\) からその頂点へ重み \(0\) の辺を伸ばすことで \(2\) 頂点間の最短距離として答えを求めることもできます）。

このグラフは、組 \((\)今いる頂点 \(,\) 辺の反転を行った回数の偶奇\()\) を頂点としていると考えることもできます。

このグラフ上でダイクストラ法を行うことで、この問題を十分高速に解くことができます。

\(\min\lbrace N,X\rbrace+1\) 個のバケットを用意することで、全体の時間計算量を \(\Theta(N+M)\) 時間とすることもできます。

実装例は以下のようになります。 実装例では最短距離を求めるのにダイクストラ法を用いています。

#include <iostream>
#include <vector>
#include <utility>
#include <queue>

int main() {
    using namespace std;
    unsigned N, M, X;
    cin >> N >> M >> X;

    vector<vector<pair<unsigned, unsigned>>> edges(2 * N);
    
    // もとのグラフでの反転に対応する辺
    for (unsigned i{}; i < N; ++i) {
        edges[i].emplace_back(i + N, X);
        edges[i + N].emplace_back(i, X);
    }

    // もとのグラフの辺をたどることに対応する辺
    for (unsigned i{}, u, v; i < M; ++i) {
        cin >> u >> v;
        --u;
        --v;
        edges[u].emplace_back(v, 1);
        edges[v + N].emplace_back(u + N, 1);
    }

    // ダイクストラ法で最短距離を求める
    priority_queue<pair<unsigned long, unsigned>, vector<pair<unsigned long, unsigned>>, greater<>> pq;
    pq.emplace(0, 0);
    vector distance(2 * N, 5UL * N * X);
    while (!empty(pq)) {
        const auto [dist, vertex]{pq.top()};
        pq.pop();
        if (distance[vertex] < dist)
            continue;
        for (const auto& [next, cost] : edges[vertex]) if (distance[next] > dist + cost)
            pq.emplace(distance[next] = dist + cost, next);
    }

    // 頂点 N と頂点 2N への最短距離のうち大きくないほうが答え
    cout << min(distance[N - 1], distance[2 * N - 1]) << endl;
    return 0;
}