90pts dijkstra求助
  • 板块P4943 密室
  • 楼主zhoujinhong
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/26 16:10
  • 上次更新2024/1/26 18:00:51
查看原帖
90pts dijkstra求助
984450
zhoujinhong楼主2024/1/26 16:10
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50010;
int n,m,k,a[N],c,b,d,can[N],vis[N],dis1[N],dis2[N],x,y,sum1,sum2,sum3,sum4,ans;
struct node{
	int to,w;
};
vector<node>g[N];
priority_queue<pair<int,int> >q;
int minn(int u,int v){
	return u>v?v:u;
}
int maxx(int u,int v){
	return u>v?u:v;
}
void dijkstra1(int tmp){
	memset(dis1,0x3f,sizeof(dis1));
	dis1[tmp]=0;
	q.push(make_pair(0,tmp));
	while(q.size()){
		int cur=q.top().second;
		q.pop();
		if(vis[cur]) continue;
		vis[cur]=1;
		for(int i=0;i<g[cur].size();i++){
			int tmp1=g[cur][i].to;
			int tmp2=g[cur][i].w;
			if(dis1[cur]+tmp2<dis1[tmp1] && !vis[tmp1]){
				dis1[tmp1]=dis1[cur]+tmp2;
				q.push(make_pair(-dis1[tmp1],tmp1));
			}
		}
	} 
}
void dijkstra2(int tmp){
	memset(vis,0,sizeof(vis));
	memset(dis2,0x3f,sizeof(dis2));
	dis2[tmp]=0;
	q.push(make_pair(0,tmp));
	while(q.size()){
		int cur=q.top().second;
		q.pop();
		if(vis[cur]) continue;
		vis[cur]=1;
		for(int i=0;i<g[cur].size();i++){
			int tmp1=g[cur][i].to;
			int tmp2=g[cur][i].w;
			if(dis2[cur]+tmp2<dis2[tmp1] && !vis[tmp1] && !can[tmp1]){
				dis2[tmp1]=dis2[cur]+tmp2;
				q.push(make_pair(-dis2[tmp1],tmp1));
			}
		}
	} 
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	ans=LONG_LONG_MAX;
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		cin>>a[i];
		can[a[i]]=1;
	} 
	for(int i=1;i<=m;i++){
		cin>>c>>b>>d;
		g[c].push_back({b,d});
		g[b].push_back({c,d});
	}
	cin>>x>>y;
	dijkstra1(1);
	dijkstra2(1);
	ans=minn(maxx(dis1[x],dis2[y]),maxx(dis1[y],dis2[x]));
	sum1=dis1[x];
	sum2=dis1[y];
	sum3=dis2[x];
	sum4=dis2[y];
	dijkstra1(x);
	ans=minn(ans,sum1+dis1[y]);
	dijkstra1(y);
	ans=minn(ans,sum2+dis1[x]);
	dijkstra2(x);
	ans=minn(ans,sum3+dis2[y]);
	dijkstra2(y);
	ans=minn(ans,sum4+dis2[x]);
	cout<<ans;
	return 0;
}
2024/1/26 16:10
加载中...