50pts求调
  • 板块P4943 密室
  • 楼主yuanhang10
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/31 20:15
  • 上次更新2025/7/31 20:22:38
查看原帖
50pts求调
1148675
yuanhang10楼主2025/7/31 20:15
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll> 
using namespace std;
ll n,m,k,disha[50005],disluo[50005],disx[50005],a,b,c,head[50005],cnt,x,y,ans=1e9;
bool onlyharry[50005],vis[50005];
struct node{
	ll ne,to,dis;
}edge[100005<<1];
void jb(ll from,ll to,ll d){
	cnt++;
	edge[cnt].ne=head[from];
	edge[cnt].to=to;
	edge[cnt].dis=d;
	head[from]=cnt;
	return ;
}
void dijkstraluo(ll sx,ll sd){//罗恩的路线
	priority_queue<pll,vector<pll>,greater<pll> >q;
	memset(vis,0,sizeof(vis));
	disluo[sx]=sd;
	q.push(make_pair(sd,sx));
	while(q.size()){
		int hx=q.top().second;
		q.pop();
		if(vis[hx]) continue;
		vis[hx]=1;
		for(int i=head[hx];i;i=edge[i].ne){
			ll y=edge[i].to,d=edge[i].dis;
			if(onlyharry[y]) continue; //哈利能进罗恩不能进则跳过
			if(disluo[y]>disluo[hx]+d){
				disluo[y]=disluo[hx]+d;
				if(!vis[y]){
					q.push(make_pair(d,y));
				}
			}
		}
	}
	return ;
}
void dijkstraha(ll sx,ll sd){
	priority_queue<pll,vector<pll>,greater<pll> >q;
	memset(vis,0,sizeof(vis));
	disha[sx]=sd;
	q.push(make_pair(sd,sx));
	while(q.size()){
		int hx=q.top().second;
		q.pop();
		if(vis[hx]) continue;
		vis[hx]=1;
		for(int i=head[hx];i;i=edge[i].ne){
			ll y=edge[i].to,d=edge[i].dis;
			if(disha[y]>disha[hx]+d){
				disha[y]=disha[hx]+d;
				if(!vis[y]){
					q.push(make_pair(d,y));
				}
			}
		}
	}
	return ;
}
void dijkstrax(ll sx,ll sd){
	priority_queue<pll,vector<pll>,greater<pll> >q;
	memset(vis,0,sizeof(vis));
	disx[sx]=sd;
	q.push(make_pair(sd,sx));
	while(q.size()){
		int hx=q.top().second;
		q.pop();
		if(vis[hx]) continue;
		vis[hx]=1;
		for(int i=head[hx];i;i=edge[i].ne){
			ll y=edge[i].to,d=edge[i].dis;
			if(disx[y]>disx[hx]+d){
				disx[y]=disx[hx]+d;
				if(!vis[y]){
					q.push(make_pair(d,y));
				}
			}
		}
	}
}
int main(){
	memset(disha,0x3f,sizeof(disha));
	memset(disluo,0x3f,sizeof(disluo));
	memset(disx,0x3f,sizeof(disx));
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=k;i++){
		scanf("%lld",&a);
		onlyharry[a]=1;
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&a,&b,&c);
		jb(a,b,c);
		jb(b,a,c);
	}
	scanf("%lld%lld",&x,&y);
	dijkstraluo(1,0);
	dijkstraha(1,0);
	dijkstrax(x,0);
	ans=min(ans,max(disha[x],disluo[y]));
	ans=min(ans,max(disha[y],disluo[x]));
	ans=min(ans,disha[x]+disx[y]);
	ans=min(ans,disha[y]+disx[y]);
	printf("%lld",ans);
	return 0;
}

4,7,8,9,10测试点wa了
自己造了好几组数据都没测出来

2025/7/31 20:15
加载中...