WA 求调玄关
查看原帖
WA 求调玄关
830990
roumeideclown楼主2024/12/10 18:48

record

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
const int N=4e5+5;
int n,m,k;
struct enode {
	int nxt,to,val;
} edge[N*2];
int tot,head[N];
void add(int u,int v,int w) {edge[++tot]={head[u],v,w};head[u]=tot;}
int dist[N];
bool vis[N];
priority_queue<pii,vector<pii>,greater<pii>> q;
void dijkstra(int s) {
	memset(dist,0x3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	q.push({dist[s]=0,s});
	while(!q.empty()) {
		int u=q.top().se;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].nxt) {
			int v=edge[i].to,w=edge[i].val;
			if(dist[v]>dist[u]+w) q.push({dist[v]=dist[u]+w,v});
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1,u,v,w;i<=n;i++) {
		cin>>u>>v>>w;
		if(w==1) {
			add(u,v,1);
			add(v,u,1);
		}
		else {
			add(u+n,v+n,1);
			add(v+n,u+n,1);
		}
	}
	for(int i=1,x;i<=k;i++) {
		cin>>x;
		add(x,x+n,0);
		add(x+n,x,0);
	}
	dijkstra(1);
	int ans=min(dist[n],dist[n+n]);
	cout<<(ans==0x3f3f3f3f?-1:ans)<<'\n';
	return 0;
}

2024/12/10 18:48
加载中...