P1135 奇怪的电梯 题解。
首先这种简单最短路的题，首先是建图然后再是最短路，我们伟大的费用流正好可以解决这一类的问题，这道题你只需要 \(i\) 分别向 \(i \pm K_i\) 连 \((1, 1)\) 的边然后跑最小费用最大流就可以轻松解决这个问题了。
但是这道题有一点不一样，直接跑可能流量大于 \(1\)，但是最短路是只能有一条的，可恶的最短路，可惜就算你路径有几条我伟大的费用流也能跑出正确最短路，怎么做呢？
我们只需要建一个新的汇点 \(B'\) 然后 \(B\) 向 \(B'\) 连 \((1, 0)\) 的边，而最短路只能有一条？根本不在乎，我们直接这样连边，流量就不超过 \(1\) 了，这样做就是对的，这世间，还有什么能够阻挡！！！！！还有什么能够阻挡我们的费用流算法！！！！！！！！！
时间复杂度 \(O(n^3)\)，可能还有一点小常数不过没有人在乎，这就是网络流算法的魅力，BFS 这种逆时代浪潮的做法迟早被淹没在费用流恐怖的实力之下！！！
大概就是上面这样。
#include <bit>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
using u32 = unsigned;
using p32 = pair<int, int>;
const int N = 205, M = 405, INF = 0x3f3f3f3f;
int n, s, t, tt, a[N], h[N], dis[N], pos[N], siz[35], cur[N], head[N],
cnt = 1, beg, top, flow, cost;
bool vis[N];
struct edge {
int to, nex, w, c;
} e[M << 1];
queue<int> Q;
vector<int> buc[35], tmp;
void add(int u, int v, int w, int c) { e[++cnt] = {v, head[u], w, c}, head[u] = cnt; }
void addflow(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }
void spfa() {
memset(h, 0x3f, sizeof(h));
h[s] = 0, vis[s] = true, Q.push(s);
while (!Q.empty()) {
int u = Q.front();
vis[u] = false, Q.pop();
for (int i = head[u]; i; i = e[i].nex) {
int v = e[i].to, w = e[i].w, c = e[i].c;
if (h[v] > h[u] + c && w) {
h[v] = h[u] + c;
if (!vis[v]) vis[v] = true, Q.push(v);
}
}
}
}
// radix heap
void insert(int x) {
int k = bit_width<u32>(dis[x] ^ dis[top]);
++siz[k], pos[x] = buc[k].size(), buc[k].push_back(x);
}
void update(int x, int y) {
int k = bit_width<u32>(dis[x] ^ dis[top]);
--siz[k], dis[x] = y, insert(x);
}
void removemin() {
pos[top] = -1, --siz[0];
if (siz[0]) {
while (pos[top = buc[0][beg]] == -1) ++beg;
return;
}
int cur = 0, las = top;
for (int i = 30; i >= 1; i--)
if (siz[i]) cur = i;
siz[cur] = beg = top = 0, tmp = move(buc[cur]);
for (int i = 0; i <= cur; i++) buc[i].clear();
for (int i = 0; i < (int)tmp.size(); i++) {
int k = bit_width<u32>(dis[tmp[i]] ^ dis[las]);
if (k == cur && pos[tmp[i]] == i && dis[tmp[i]] < dis[top]) top = tmp[i];
}
for (int i = 0; i < (int)tmp.size(); i++) {
int k = bit_width<u32>(dis[tmp[i]] ^ dis[las]);
if (k == cur && pos[tmp[i]] == i) insert(tmp[i]);
}
}
bool dijkstra() {
memset(dis, 0x3f, sizeof(dis));
dis[top = s] = beg = 0;
for (int i = 0; i <= 30; i++) siz[i] = 0, buc[i].clear();
for (int i = 1; i <= n + 1; i++) insert(i);
for (int i = 1; i <= n + 1; i++, removemin()) {
if (dis[top] == INF) break;
for (int j = head[top]; j; j = e[j].nex) {
int v = e[j].to, w = e[j].w, c = e[j].c;
if (dis[v] > dis[top] + c + h[top] - h[v] && w)
update(v, dis[top] + c + h[top] - h[v]);
}
}
return dis[t] != INF;
}
int dfs(int u, int flow) {
if (u == t) return flow;
int used = 0;
vis[u] = true;
for (int &i = cur[u]; i; i = e[i].nex) {
int v = e[i].to, w = e[i].w, c = e[i].c;
if (!vis[v] && dis[v] == dis[u] + c + h[u] - h[v] && w) {
int ret = dfs(v, min(flow - used, w));
used += ret, e[i].w -= ret, e[i ^ 1].w += ret;
if (used == flow) break;
}
}
vis[u] = false;
return used;
}
void dinic() {
int ret;
spfa();
while (dijkstra()) {
memcpy(cur, head, sizeof(cur));
memset(vis, 0, sizeof(vis));
while ((ret = dfs(s, INF))) flow += ret, cost += ret * (dis[t] + h[t]);
for (int i = 1; i <= n + 1; i++) h[i] += dis[i];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s >> tt, t = n + 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i - a[i] >= 1) addflow(i, i - a[i], 1, 1);
if (i + a[i] <= n) addflow(i, i + a[i], 1, 1);
}
addflow(tt, t, 1, 0);
dinic();
if (flow == 1) cout << cost;
else cout << "-1";
return 0;
}