MLE?
查看原帖
MLE?
19228
蒟蒻炒扇贝楼主2021/9/14 17:34
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
#define int long long
#define pir pair<int,int>
const int MAXN=1e5+5;
struct edge
{
	int v,nxt;
}a[MAXN*4];
int n,m,s,k,c,e,head[MAXN],dan[MAXN],cnt,dis[MAXN],vis[MAXN];
void addedge(int u,int v)
{
	a[++cnt].v=v;
	a[cnt].nxt=head[u];
	head[u]=cnt;
}
struct node
{
	int u,s;
};
queue<node>q;
void bfs()
{
	while(!q.empty())
	{
		int now=q.front().u,dep=q.front().s;
		q.pop();
		if(dan[now]!=-1)dan[now]=1;
		if(dep+1>s)continue;
		for(int i=head[now];i;i=a[i].nxt)
		{
			int to=a[i].v;
			q.push(node{to,dep+1});
		}
	}
}
void dij(int s)
{
	priority_queue<pir,vector<pir>,greater<pir> >q;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push(pir(0,s));
	while(!q.empty())
	{
		int now=q.top().second;
		q.pop();
		if(dan[now]==-1)continue;
		if(vis[now])continue;
		vis[now]=1;
		for(int i=head[now];i;i=a[i].nxt)
		{
			int to=a[i].v,w;
			if(dan[to])w=e;
			else w=c;
			if(dis[now]+w<dis[to])
			{
				dis[to]=dis[now]+w;
				q.push(pir(dis[to],to));
			}
		}
	}
}
signed main()
{
	cin>>n>>m>>k>>s>>c>>e;
	for(int i=1;i<=k;i++)
	{
		int x;
		scanf("%lld",&x);
		dan[x]=-1;
		q.push(node{x,0});
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	bfs();
	dij(1);
	int ans=dis[n];
	if(dan[n])ans-=e;
	else ans-=c;
	cout<<ans;
	return 0;
}

我数组空间明明开的是最小的啊/kk

2021/9/14 17:34
加载中...