#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
struct node
{
long long v,w;
};
vector<node> e[400005];
long long dis[400005];
bool vis[400005];
int n,m,x;
void dijkstra(int s)
{
for(int i = 1;i <= 400000;i++)
{
dis[i] = 9e10;
}
dis[s] = 0;
priority_queue<pair<long long,int>,
vector<pair<long long,int>>,
greater<pair<long long,int>>> q;
q.push({0,s});
while(!q.empty())
{
auto u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto ed : e[u])
{
int v = ed.v;
int w = ed.w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
q.push({dis[v],v});
}
}
}
}
int main()
{
cin >> n >> m >> x;
while(m--)
{
int u,v;
cin >> u >> v;
e[u].push_back({v,1});
e[v + n].push_back({u + n,1});
}
for(int i = 1;i <= n;i++)
{
e[i].push_back({i + n,x});
e[i + n].push_back({i,x});
}
dijkstra(1);
cout << min(dis[n],dis[n + n]) << endl;
return 0;
}
ABC395 E题求条
qwq
