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<热门推荐信息
By白云如幻
一、AI创作系统 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统,支持OpenAI-GPT全模型+国内AI全模型。本期针对源码系统整体测试下来非常完 ...
Byqq_58647543
Dockerfile简介 从之前的学习中我们可以了解到:镜像的定制实际上就是定制每一层所添加的配置、文件。那么如果我们可以把每一层修改、安装、构建、操作的命令都写入一个脚本,用这个脚本来构建、定制镜像 ...
By望天hous
在 C# 中,如果使用 TcpClient 或 TcpListener 这样的套接字进行通信,并且网络连接断开,不发送心跳是无法立即检测到断开的。这是因为 TCP 协议本身没有内置的机制来检测连接是否 ...
By乱蜂朝王
github地址:https://github.com/AvenSun/OpenCvSharpSlim Slim Build of OpenCvSharp OpenCvSharpSlim This p ...
By清浊-
在Ubuntu 22.04 中,网络配置已迁移到 Netplan,因此可以使用 Netplan 配置文件来手动设置 IP 地址并关闭 DHCP。 以下是在 Ubuntu 22.04 上手动设置 IP ...