求助!
查看原帖
求助!
168662
YangFanQH楼主2022/8/15 13:14

为什么WA第四个点?

#include<iostream>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=100009,INF=1000000009;
bool b[N],inq[N];
int n,m,k,s,p,q,x,y,stp[N],dis[N],cst[N],c[N];
vector<int> v[N];
queue<int> qq;
inline int read()
{
	register int x=0;
	char c=getchar();
	while(c>'9'||c<'0') c=getchar();
	while('0'<=c&&c<='9') x=x*10+c-48,c=getchar();
	return x;
}
void dfs(int u)
{
	if(stp[u]==s) return ;
	for(int i=0;i<v[u].size();i++)
		if(!b[v[u][i]]&&stp[v[u][i]]>stp[u]+1) stp[v[u][i]]=stp[u]+1,cst[v[u][i]]=q,dfs(v[u][i]);
}
void spfa()
{
	for(int i=1;i<=n;i++) dis[i]=INF;
	qq.push(1);inq[1]=1;dis[1]=0;
	while(!qq.empty())
	{
		int u=qq.front();qq.pop();inq[u]=0;
		for(int i=0;i<v[u].size();i++)
			if(!b[v[u][i]])
				if(dis[v[u][i]]>dis[u]+cst[v[u][i]])
				{
					dis[v[u][i]]=dis[u]+cst[v[u][i]];
					if(!inq[v[u][i]]) qq.push(v[u][i]),inq[v[u][i]]=1;
                }
    }
    cout<<dis[n]<<endl;
}
signed main()
{
	freopen("p3393.in","r",stdin);
	freopen("p3393.out","w",stdout);
	n=read(),m=read(),k=read(),s=read(),p=read(),q=read();
	for(int i=2;i<=n-1;i++)cst[i]=p;
	for(int i=1;i<=k;i++) c[i]=read(),b[c[i]]=1;
	for(int i=1;i<=m;i++) x=read(),y=read(),v[x].push_back(y),v[y].push_back(x);
	memset(stp,0x3f,sizeof(stp));
    for(int i=1;i<=k;i++) stp[c[i]]=0,dfs(c[i]);
	cst[n]=0;spfa();
	return 0;
}

2022/8/15 13:14
加载中...