#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
加载中... 加载中...
