题意
有一张 n n n 点 m m m 边的无向图,点有点权,同时给定一个集合 T T T, T T T 中的点都不允许经过。对于一个点 i i i,如果它与 T T T 中的任意一个点相距边数 ≤ S \le S ≤S 条,那么点 i i i 的权值为 q q q,否则为 p p p。求 1 → n 1 \to n 1→n 的最短路。(点 n n n 的权值不计算在内)
思路
定义 s a f e i safe_i safei 表示点 i i i 的状态,具体如下:
- s a f e i = − 1 safe_i=-1 safei=−1:点 i i i 在集合 T T T 中,不允许经过;
- s a f e i = 0 safe_i=0 safei=0:点 i i i 与 T T T 中的任意一个点相距边数 ≤ S \le S ≤S 条,权值为 q q q;
- s a f e i = 1 safe_i=1 safei=1:点 i i i 不满足上面两种情况,权值为 p p p。
然后,将 T T T 中的点全部加入队列中,限制 S S S 步进行 bfs,就可以得到 s a f e safe safe 数组。
求出 s a f e safe safe 后,跑一遍点权最短路即可,但这样会算上 n n n 的权值,要减掉。
另外本题需要开 long long
,INF 也要相应变大。
代码
// Problem: P3393 逃离僵尸岛
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3393
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <queue>
using namespace std;
#define int long long
const int INF = 1e18;
using PII = pair<int, int>;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m, k, s, P, Q;
cin >> n >> m >> k >> s >> P >> Q;
vector<vector<int>> G(n);
vector<int> safe(n, 1);
queue<PII> q;
for(int i = 0, x; i < k; i++){
cin >> x;
x--;
safe[x] = -1;
q.emplace(x, 0);
}
for(int i = 0, u, v; i < m; i++){
cin >> u >> v;
u--, v--;
G[u].push_back(v);
G[v].push_back(u);
}
while(q.size()){
PII t = q.front();
q.pop();
int u = t.first, dis = t.second;
for(auto &v: G[u])
if(dis < s && safe[v] == 1){
safe[v] = 0;
q.emplace(v, dis + 1);
}
}
vector<int> dis(n, INF);
vector<bool> vis(n, false);
auto dij = [&](int s){
priority_queue<PII, vector<PII>, greater<PII>> pq;
dis[s] = 0;
pq.emplace(0, s);
while(pq.size()){
int u = pq.top().second;
pq.pop();
for(auto &v: G[u]){
if(safe[v] == -1) continue;
int w = (safe[v] == 1? P : Q);
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
pq.emplace(dis[v], v);
}
}
}
};
dij(0);
int ans = dis[n - 1] - (safe[n - 1] == 1? P: Q);
cout << ans << endl;
return 0;
}