28pts
查看原帖
28pts
757946
gaolangwen_is_sb楼主2023/4/19 18:44

只A了#1,#3。

求助dalao。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
struct Node
{
	int to,step;
};
int n,m,k,s,p,Q,w[N],dis[N];
bool vis[N];
queue<Node>q;
vector<int>nbr[N];
void bfs()
{
	while(!q.empty())
	{
		Node cur=q.front();
		q.pop();
		if(cur.step>=s)
			continue;
		for(int i=0;i<nbr[cur.to].size();i++)
		{
			int nxt=nbr[cur.to][i];
			if(vis[nxt]==false)
			{
				q.push((Node){nxt,cur.step+1});
				vis[nxt]=true;
				w[nxt]=Q;
			}
		}
	}
	return ;
}
void dijkstra(int s)
{
	memset(vis,0,sizeof vis);
	memset(dis,0x3f,sizeof dis);
	priority_queue<int,vector<int>,greater<int> >pq;
	pq.push(s);
	dis[s]=0;
	while(pq.empty()==false)
	{
		int cur=pq.top();
		pq.pop();
		if(vis[cur]==true)
			continue;
		vis[cur]=true;
		for(int i=0;i<nbr[cur].size();i++)
		{
			int nxt=nbr[cur][i],val=w[nxt];
			if(dis[cur]+val<dis[nxt])
			{
				dis[nxt]=dis[cur]+val;
				pq.push(nxt);
			}
		}
	}
	return ;
}
signed main()
{
	cin>>n>>m>>k>>s>>p>>Q;
	for(int i=1;i<=n;i++)
		w[i]=p;
	for(int i=1;i<=k;i++)
	{
		int f;
		cin>>f;
		w[f]=1e9;
		vis[f]=1;
		q.push((Node){f,0});
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		nbr[x].push_back(y);
		nbr[y].push_back(x);
	}
	bfs();
	w[n]=w[1]=0;
	dijkstra(1);
	cout<<dis[n];
	return 0;
}
2023/4/19 18:44
加载中...