洛谷 P5340 大中锋的游乐场
题意
给出一张 \(n\) 个点 \(m\) 条边的图，每个点有一个点权 \(1\) 或 \(-1\)。
给出点 \(s,t\)，求出 \((s,t)\) 间满足以下条件的最短路。
任意时刻，走过的路径上点权和均 \(\in[-k,k]\)。
思路
分层图最短路。
\(dis_{i,j}\) 表示走到 \(i\)，点权和为 \(j\) 的最短路。
跑一遍 dijkstra，顺便转移即可。
将点权全部加 \(k\) 方便数组存储。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int ver[N << 1], nxt[N << 1], head[N], edge[N << 1], tot;
int n, m, k, s, t, dis[N][22], a[N];
bool vis[N][25];
struct node {int x, y, d;};
bool operator < (node A, node B) {return A.d > B.d;}
priority_queue <node> Q;
void add(int x, int y, int z) {
ver[++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
edge[tot] = z;
}
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
if (a[i] == 2) a[i] = -1;
}
for (int i = 1, u, v, w; i <= m; i ++) {
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
cin >> s >> t;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s][k + a[s]] = 0;
Q.push({s, k + a[s], 0});
while (!Q.empty()) {
int x = Q.top().x, y = Q.top().y; Q.pop();
if (vis[x][y]) continue;
vis[x][y] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int to = ver[i]; int state = y + a[to];
if (state < 0 || state > 2 * k) continue;
if (dis[to][state] > dis[x][y] + edge[i]) {
dis[to][state] = dis[x][y] + edge[i];
Q.push({to, state, dis[to][state]});
}
}
}
int ans = 0x3f3f3f3f;
for (int i = 0; i <= 2 * k; i ++)
ans = min(ans, dis[t][i]);
if (ans == 0x3f3f3f3f) ans = -1;
cout << ans << "\n";
}
int main() {
int T;
cin >> T;
while (T --)
solve();
return 0;
}