MLE求调
查看原帖
MLE求调
1124323
A_small_WA楼主2024/9/5 23:03

rt,

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,k,p,q,u,v,c[114514],mdis[114514],low[114514];
bool jha[114514],dg[114514];
vector <int> vt[114514];
struct node{
	int now,dis;
};
struct cmp{
	bool operator()(const node &a,const node &b){
		return a.dis>b.dis;
	}
};
queue <node> q1;
priority_queue <node,vector<node>,cmp> pq;
void bfs(int kw){
	node nw,nx;
	while(q1.size()){
		nw=q1.front();
		q1.pop();
		if(nw.dis>s||nw.now==n||dg[nw.now]&&kw!=nw.now) continue;
		low[nw.now]=1;
		for(int i=0;i<vt[nw.now].size();i++){
			nx.now=vt[nw.now][i],nx.dis=nw.dis+1;
			q1.push(nx);
		}
	}
	return;
}
void dij(){
	node stt;stt.dis=0,stt.now=1;
	pq.push(stt);
	node nw,nx;
	while(pq.size()){
		nw=pq.top();
		pq.pop();
		if(jha[nw.now]||dg[nw.now]) continue;
		jha[nw.now]=1;
		for(int i=0;i<vt[nw.now].size();i++){
			if(jha[vt[nw.now][i]]) continue;
			int dt=nw.dis;
			if(low[vt[nw.now][i]]) dt+=q;
			else dt+=p;
			if(dt<mdis[vt[nw.now][i]]){
				mdis[vt[nw.now][i]]=dt;
				nx.dis=dt,nx.now=vt[nw.now][i];
				pq.push(nx);
			}
		}
	}
}
signed main(){
	cin>>n>>m>>k>>s>>p>>q;
	for(int i=1;i<=k;i++) cin>>c[i];
	for(int i=1;i<=n;i++) mdis[i]=1e18;
	mdis[1]=0;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		vt[u].push_back(v);
		vt[v].push_back(u);
	}
	for(int i=1;i<=k;i++){
		dg[c[i]]=1;
		node stt1;
		stt1.dis=0,stt1.now=c[i];
		q1.push(stt1);
		bfs(c[i]);
	}
	dij();
	cout<<mdis[n]-p;
	return 0;
}

第 6,76,7 个点都 MLE 了,是 bfs 的问题,但不会改,求大佬帮忙。

2024/9/5 23:03
加载中...