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_queue 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;i<=K;i++) cin>>c[i],add(0,c[i],1),add(c[i],0,1); for(int i=1;i<=M;i++) cin>>a[i]>>b[i],add(a[i],b[i],1),add(b[i],a[i],1); dij(0); for(int i=1;i<=N;i++) if(dis[i]<=S+1) danger[i]=1; cnt=0; for(int i=1;i<=M;i++) head[i]=0,nxt[i]=0,w[i]=0,vis[i]=0; for(int i=1;i<=K;i++) vis[c[i]]=1; int tmp; for(int i=1;i<=M;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]) cout<热门推荐信息
ByCyberSecurity_zhang
目录 1. 概述 2. 测量方式 -- Poll 3. 测量方式 -- DAQ 3.1 ODT概念模型 3.2 DAQ List概念 3.3 ODT 绝对编号和相对编号 3.4 静态DAQ和动态DAQ ...
By逃逸的卡路里
UG软件版本这里咱们就不提了，大部分伙伴应该都是钩子激活软件，肯定会遇到或多或少的安装问题，今天这里给大家总结了下，需要的小伙伴自取。 有其他问题可以一起讨论，也希望看到的小伙伴多关注支持哦。 安装U ...
By听海边涛声
如果矩阵A可逆，那么它的逆矩阵也可逆，并且如果矩阵A可逆，假设是一个不为0的数，那么也可逆，并且如果矩阵A和都可逆，而且它们的阶数也相同，那么它们的乘积也是可逆的，并且如果矩阵A可逆，那么它的行列式的 ...
ByFanly
WildCard提供了一款受欢迎的国际虚拟信用卡（wildcard），适用于跨境支付和购买外部服务。相较于传统信用卡，它更为灵活且 ...
ByFanly
WildCard虚拟信用卡（wildcard）为跨境电商和海外购物提供了安全、便捷的支付解决方案。无需实体银行卡，用户可以轻松完成 ...
