P3393 逃离僵尸岛 bfs +最短路

本文主要是介绍P3393 逃离僵尸岛 bfs +最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P3393 逃离僵尸岛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：bfs处理出高收费城市，将价格作为点权，将点权当作边权跑最短路。由于到达 $v$ ，且 $v$ 不是终点，那么还要再走这个时候需要在该点休息，但是如果是终点就不用再休息，可以将终点点权为0。

易错点：

开long long
bfs没用设置vis数组（脑子糊涂了，想着不全部遍历一遍可能有遗漏，却忘了bfs的性质，第一次到该点就是最小步数（后来者不能居上
注意点权的设置：已经被僵尸控制的城市是不能到达的，危险城市是 $Q$ ，普通城市是 $P$ ，终点是0。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 4e5 + 21;
struct no {int u;LL d;bool operator<(const no& rhs) const {return d > rhs.d;}
};
int e[N], ne[N], h[N], idx,w[N],vis[N];
LL dis[N];
void add(int u, int v) {e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int main()
{int n,m,K,S; cin>>n>>m>>K>>S;int P,Q; cin>>P>>Q;queue<no> q;for(int i = 0, x; i < K; ++i) {cin>>x;vis[x] = 1;w[x] = -1;q.push({x, 0});}memset(h, -1, sizeof(h));for(int i = 0; i < m; ++i) {int u,v; cin>>u>>v;add(u,v), add(v, u);}// bfswhile(q.size()) {auto tmp = q.front(); q.pop();int u = tmp.u, d = tmp.d;if(d > S) continue;for(int i = h[u]; ~i; i = ne[i]) {int y = e[i];if(vis[y]) continue;if(d + 1 <= S) {vis[y] = 1;q.push({y, d + 1});}}}// 设置点权for(int i = 1; i <= n; ++i) {if(w[i] == -1) continue;w[i] = vis[i] ? Q : P;}for(int i = 1; i <= n; ++i) {dis[i] = 1e18;vis[i] = 0;}dis[1] = 0;w[n] = 0;// dijkstrapriority_queue<no> heap;heap.push({1, 0});while(heap.size()) {auto tmp = heap.top(); heap.pop();int u = tmp.u, d = tmp.d;if(vis[u]) continue;vis[u] = 1;for(int i = h[u]; ~i; i = ne[i]) {int y = e[i];if(w[y] == -1) continue;if(dis[y] > dis[u] + w[y]) {dis[y] = dis[u] + w[y];heap.push({y, dis[y]});}}}cout<<dis[n];
}