This problem can be solved by transforming the given graph into another graph, and finding the shortest distance on the new graph. (This technique is so-called “extended Dijkstra.”)

Consider a weighted directed graph with \(2N\) vertices and \(N+2M\) edges specified as follows. (The \(2N\) vertices are labeled vertex \(1, \ldots, \) vertex \(2N\).)

• Corresponding to each edge \((u, v)\) in the given graph, there are an edge \((u,v)\) of weight \(1\) and edge \((v+N,u+N)\) of weight \(1\).
• There are an edge \((u,u+N)\) of weight \(X\) and an edge \((u+N,u)\) of weight \(X\).
• There are no other edges.

The answer is the shortest distance from vertex \(1\) to vertex \(N\) or from vertex \(1\) to vertex \(2N\), whichever is smaller. (It can be interpreted as the shortest distance between problem by adding a vertex, and edges of weight \(0\) from vertex \(N\) and \(2N\) to that vertex.)

The vertices of this graph can be seen as representing the pairs \((\)current vertex\(,\) the parity of the number of times the edges were flipped\()\).

The problem can be solved fast enough by performing Dijkstra’s algorithm on it.

The time complexity can be optionally reduced to \(\Theta(N+M)\) time by using \(\min\lbrace N,X\rbrace+1\) buckets.

Sample code is shown below. In this sample code, we use Dijkstra’s algorithm to find the shortest distance.

#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);
    
    // Edges corresponding to edge reversal on the original graph
    for (unsigned i{}; i < N; ++i) {
        edges[i].emplace_back(i + N, X);
        edges[i + N].emplace_back(i, X);
    }

    // Edges corresponding to following the edges in the original graph
    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);
    }

    // Use Dijkstra's algorithm to find the shortest distance
    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);
    }

    // The answer is the shortest distance to vertex N or 2N, whichever is smaller
    cout << min(distance[N - 1], distance[2 * N - 1]) << endl;
    return 0;
}