网络常识

    P3393 逃离僵尸岛

    拧错位置的螺丝钉2023年11月03日
    收录于话题
    #图论2

    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<

    相关信息

    你可能还喜欢

    热门推荐信息

    初识Dockerfile

    Byqq_58647543

    Dockerfile简介 从之前的学习中我们可以了解到：镜像的定制实际上就是定制每一层所添加的配置、文件。那么如果我们可以把每一层修改、安装、构建、操作的命令都写入一个脚本，用这个脚本来构建、定制镜像 ...