分层图Dij, 其实很板
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int N = 2e5 + 10;
int head[N], nx[2*N], to[2*N];
int head2[N], nx2[2*N], to2[2*N];
int id = 1, id2 = 1;
const int inf = 1e18;
void ad(int x, int y) {
to[id] = y;
nx[id] = head[x];
head[x] = id++;
to2[id2] = x;
nx2[id2] = head2[y];
head2[y] = id2++;
}
int dis[2][N];
bool vis[2][N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, x;
cin >> n >> m >> x;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
ad(u, v);
}
struct node {
int p, cost;
bool f;
bool operator<(const node& b) const {
return cost > b.cost;
}
};
for (int i = 1; i <= n; i++) {
dis[0][i] = dis[1][i] = inf;
}
dis[0][1] = dis[1][1] = 0;
priority_queue<node> q;
q.push({1,0,1});
while (q.size()) {
node cur = q.top();
q.pop();
if (vis[cur.f][cur.p]) {
continue;
}
vis[cur.f][cur.p] = true;
int now = cur.p;
bool tp = cur.f;
// 1表示没有反转
for (int i = head[now]; i; i = nx[i]) {
if (tp == 1) {
if (dis[1][now] + 1 < dis[1][to[i]]) {
dis[1][to[i]] = dis[1][now] + 1;
q.push({to[i],dis[1][to[i]],1});
}
} else {
if (dis[0][now] + 1 + x < dis[1][to[i]]) {
dis[1][to[i]] = dis[0][now] + 1 + x;
q.push({to[i],dis[1][to[i]],1});
}
}
}
for (int i = head2[now]; i; i = nx2[i]) {
if (tp == 0) {
if (dis[0][now] + 1 < dis[0][to2[i]]) {
dis[0][to2[i]] = dis[0][now] + 1;
q.push({to2[i],dis[0][to2[i]],0});
}
} else {
if (dis[1][now] + 1 + x < dis[0][to2[i]]) {
dis[0][to2[i]] = dis[1][now] + 1 + x;
q.push({to2[i],dis[0][to2[i]],0});
}
}
}
}
cout << min(dis[1][n],dis[0][n]);
return 0;
}