题解 P3393 【逃离僵尸岛】

顾z

2018-10-09 17:52:52

Solution

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 题目描述--->[p3393 逃离僵尸岛](https://www.luogu.org/problemnew/show/P3393) 刷题有益于身心健康. 还有,谁说这是个简单题了 emm ### 分析 明显最短路的题。 但是需要注意的是有一些传染源,这些传染源会控制一些点. 我们需要$Bfs$处理出这些点,标记它们是$Safe$与否。 这里给出一些定义. - $Safe[i]==1$代表城市安全,居住价钱为$P$ - $Safe[i]==-1$表示城市为传染源,不可居住. - $Safe[i]==0$表示城市危险,居住价钱为$Q$. 这个时候预处理出来之后直接跑最短路就行. 但是需要注意的是,跑完最短路之后我们会在$n$点居住。($Dijkstra$吼啊 所以需要减去$n$位置的价值。 **注意需要判断$n$点是否安全,而决定我们减去哪个费用** 如果$Wa$掉#4和#6的话需要**将极大值赋的足够大.** 还有 记得开$long \ long $! ## 代码 ```c++ #include<cstdio> #include<queue> #include<cctype> #define N 1000008 #define R register #define int long long using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,m,k,S,c[N],head[N],tot,safe[N]; int p,Q,dis[N]; bool vis[N]; struct cod{int u,v;}edge[N<<4]; inline void add(int x,int y) { edge[++tot].u=head[x]; edge[tot].v=y; head[x]=tot; } struct coc{int u,dis;}; queue<coc>q1;//结构体版bfs inline void bfs() { while(!q1.empty()) { int u=q1.front().u,dis=q1.front().dis; q1.pop(); for(R int i=head[u];i;i=edge[i].u) { if(dis<S and safe[edge[i].v]==1) { safe[edge[i].v]=0; q1.push((coc){edge[i].v,dis+1}); } } } } struct hop{ int u,d; bool operator<(const hop&a)const { return d>a.d; } }; inline void dij()//dijkstra { for(R int i=1;i<=n;i++)dis[i]=21474836476666; priority_queue<hop>q; q.push((hop){1,0});dis[1]=0; while(!q.empty()) { int u=q.top().u;q.pop(); if(vis[u])continue; vis[u]=true; for(R int i=head[u];i;i=edge[i].u) { if(safe[edge[i].v]==-1)continue;//如果-1不可居住 if(safe[edge[i].v]==0) if(dis[edge[i].v]>dis[u]+Q) { dis[edge[i].v]=dis[u]+Q; q.push((hop){edge[i].v,dis[edge[i].v]}); } if(safe[edge[i].v]==1) if(dis[edge[i].v]>dis[u]+p) { dis[edge[i].v]=dis[u]+p; q.push((hop){edge[i].v,dis[edge[i].v]}); } } } } signed main() { in(n),in(m),in(k),in(S); in(p),in(Q); for(R int i=1;i<=n;i++)safe[i]=1;//刚开始都是安全的. for(R int i=1;i<=k;i++) { in(c[i]),safe[c[i]]=-1;//标记为不安全 q1.push((coc){c[i],0}); } for(R int i=1,x,y;i<=m;i++) { in(x),in(y); add(x,y);add(y,x); } bfs();dij(); if(safe[n]==0)dis[n]-=Q; else dis[n]-=p;//判断是n是哪种城市 printf("%lld",dis[n]); return 0; } ```