Submission #36429536

---

Source Code Expand

#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<functional>
using namespace std;
bool flag[200002];
int f[200002][2];
vector<pair<int,bool>> edg[200002];
priority_queue<pair<int,pair<int,bool>>,vector<pair<int,pair<int,bool>>>,greater<pair<int,pair<int,bool>>>> heap;
inline void Update(const int pos,const bool ty,const int va)
{
	if(f[pos][ty]>va)
	{
		f[pos][ty]=va;
		heap.emplace(va,make_pair(pos,ty));
	}
	return;
}
int main()
{
	int n,m,K;
	cin>>n>>m>>K;
	for(int i=1;i<=m;++i)
	{
		int u,v,a;
		cin>>u>>v>>a;
		edg[u].emplace_back(v,a);
		edg[v].emplace_back(u,a);
	}
	for(int i=1;i<=K;++i)
	{
		int s;
		cin>>s;
		flag[s]=1;
	}
	for(int i=1;i<=n;++i)f[i][0]=f[i][1]=0x3f3f3f3f;
	f[1][1]=0;
	heap.emplace(0,make_pair(1,1));
	while(!heap.empty())
	{
		while(!heap.empty()&&f[heap.top().second.first][heap.top().second.second]!=heap.top().first)heap.pop();
		if(heap.empty()) break;
		const pair<int,bool> pos=heap.top().second;
		heap.pop();
		if(flag[pos.first])
		{
			Update(pos.first,!pos.second,f[pos.first][pos.second]);
		}
		for(auto &i:edg[pos.first])
		{
			if(i.second==pos.second)
			Update(i.first,pos.second,f[pos.first][pos.second]+1);
		}
	}
	int ans=min(f[n][0],f[n][1]);
	cout<<(ans==0x3f3f3f3f?-1:ans);
	return 0;
}

Submission Info

Judge Result