Portal.
建一个虚拟节点
0
0
0 号节点（一种很常用的思路），把这个点与所有被僵尸占领的点都连一条边权为
1
1
1 的边，跑一遍从
0
0
0 开始的 Dijkstra，对于一个点如果得到的 dis 数组值小于等于
S
+
1
S+1
S+1，那么就是危险城市。
然后跑一遍 Dijkstra，如果到达点为危险城市，边权为
Q
Q
Q；如果到达点为起点或终点，边权为
0
服务器托管网
0
0；如果到达点为僵尸占领的点时，边权为
+
∞
+infty
+∞。
代码如下：
#include
using namespace std;
#define int long long
const int maxn=600005;
int cnt,dis[maxn],a[maxn],b[maxn],head[maxn],nxt[maxn],to[maxn],w[maxn],N,M,K,S,c[maxn],P,Q;
bool danger[maxn],vis[maxn];
void add(int x,int y,int z)
{
to[++cnt]=y;
w[cnt]=z;
nxt[cnt]=head[x];
head[x]=cnt;
}
struct node
{
int id,dis;
friend bool operator (node a,node b)
{
return a.dis>b.dis;
}
};
priority_queuenode> q;
void dij(int s)
{
memset(vis,0,sizeof(vis));
memset(dis,0x3f3f3f,sizeof(dis));
dis[s]=0;q.push(node{s,0});
while(!q.empty())
{
int u=q.top().id;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=nxt[i])
if(dis[to[i]]>dis[u]+w[i]&&!vis[to[i]])
dis[to[i]]=dis[u]+w[i],q.push(node{to[i],dis[to[i]]});
}
}
signed main()
{
cin>>N>>M>>K>>S;
cin>>P>>Q;
for(int i=1;iK;i++) cin>>c[i],add(0,c[i],1),add(c[i],0,1);
for(int i=1;iM;i++) cin>>a[i]>>b[i],add(a[i],b[i],1),add(b[i],a[i],1);
dij(0);
for(int i=1;iN;i++) if(dis[i]S+1) danger[i]=1;
cnt=0;
for(int i=1;iM;i++) head[i]=0,nxt[i]=0,w[i]=0,vis[i]=0;
for(int i=1;iK;i++) vis[c[i]]=1;
int tmp;
for(int i=1;iM;i++)
{
if(vis[a[i]]||vis[b[i]]) continue;
if(danger[b[i]]) tmp=Q;
else tmp=P;
add(a[i],b[i],tmp);
if(danger[a[i]]) tmp=Q;
else tmp=P;
add(b[i],a[i],tmp);
}
dij(1);
if(!danger[N]) coutdis[N]-P;
else coutdis[N]-Q;
return 0;
}
服务器托管，北京服务器托管，服务服务器托管网器租用 http://www.fwqtg.net
相关推荐: 【JVM】synchronized锁升级的过程如何从无锁状态到偏向锁状态：偏向锁升级为轻量级锁：轻量级锁到自旋锁的状态：自旋锁升级为重量级锁：
目录 如何从无锁状态到偏向锁状态： 偏向锁升级为轻量级锁： 轻量级锁到自旋锁的状态： 自旋锁升级为重量级锁： 下面是自旋锁升级到重量级锁的过程： 重量级锁的特点如下： synchronized锁分为三种状态——偏向锁、轻量级锁、重量级锁 如何从无锁状态到偏向锁…
