题意
（很复杂，真的不想概括，以下是原题面）
在幻想乡，伊吹萃香是能够控制物体密度的鬼王。因为能够控制密度，所以萃香能够制造白洞和黑洞，并可以随时改变它们。某一天萃香闲着无聊，在妖怪之山上设置了一些白洞或黑洞，由于引力的影响，给妖怪们带来了很大的麻烦。于是他们决定找出一条消耗体力最少的路，来方便进出。已知妖怪之山上有 \(N\) 个路口(编号 \(1\)..\(N\) )，每个路口都被萃香设置了一定质量白洞或者黑洞。原本在各个路口之间有M条单向路，走过每一条路需要消耗一定量的体力以及 \(1\) 个单位的时间。由于白洞和黑洞的存在，走过每条路需要消耗的体力也就产生了变化，假设一条道路两端路口黑白洞的质量差为 \(delta\)：
-
从有白洞的路口走向有黑洞的路口，消耗的体力值减少 \(delta\)，若该条路径消耗的体力值变为负数的话，取为 \(0\)。
-
从有黑洞的路口走向有白洞的路口，消耗的体力值增加 \(delta\)。
-
如果路口两端均为白洞或黑洞，消耗的体力值无变化。
由于光是放置黑洞白洞不足以体现萃香的强大，所以她决定每过 \(1\) 个单位时间，就把所有路口的白洞改成黑洞，黑洞改成白洞。当然在走的过程中你可以选择在一个路口上停留 \(1\) 个单位的时间，如果当前路口为白洞，则不消耗体力，否则消耗 \(s_i\) 的体力。现在请你计算从路口 \(1\) 走到路口 \(N\) 最小的体力消耗。保证一定存在道路从路口 \(1\) 到路口 \(N\)。
题解
最短路，维护一个 \(f(i, h)\) 表示到达 \(i\) 点且到达之后的洞为 \(h\)。
先考虑停留的情况：
若该洞为白洞：
\[f(u, 1 - h) = f(u, h) \]为黑洞：
\[f(u, 1 - h) = f(u, h) + s_u \]（判黑白洞就用时间加最开始的形态模 \(2\)，\(1 - h\) 就是把原来的洞反过来）
如果不停留：
\[f(v, h ^ {\prime}) = \min\{f(v, h ^ {\prime}), f(u, h) + w\} \]（\(w\) 为当前消耗代价，\(h ^ {\prime}\) 为到达 \(v\) 之后的洞型）
\(w\) 可以开个函数算一下。
顺便提一嘴，如果用堆跑最短路会被卡（也有可能是我常数太大了），建议改成队列（反正也能过）。
namespace zqh {
const int N = 5005;
struct node { // 结点状态
int hol;
int wei;
int sta;
} h[N];
struct point { // 最短路的状态
int u, t, k;
};
int n, m, dis[N][2]; // 上文 f 数组
vector<pii> g[N]; // 存图
int calc(int weiu, int weiv, int holu, int holv, int w) { // 计算代价，w 为最开始的代价
if (holu == holv) {
return w;
}
if (holu == 1 && holv == 0) {
return w + abs(weiu - weiv);
}
if (holu == 0 && holv == 1) {
return max(w - abs(weiu - weiv), 0LL);
}
}
void dijkstra() { // 貌似不是 dij
memset(dis, 0x3f, sizeof dis); // 赋初值
queue<point> q;
q.push({1, 0, 0});
dis[1][h[1].hol] = 0;
while (q.size()) {
point t = q.front();
// cout << t.u << " " << t.t << " " << t.k << endl;
q.pop();
int u = t.u, hole_u = ((h[u].hol + t.t) & 1); // hole_u 为当前的洞状态
if (hole_u == 0) { // 停留，判黑白洞，赛时没盘，成功挂分
if (dis[u][1 - hole_u] > dis[u][hole_u]) {
dis[u][1 - hole_u] = dis[u][hole_u];
q.push({u, t.t + 1, dis[u][1 - hole_u]});
}
} else {
if (dis[u][1 - hole_u] > dis[u][hole_u] + h[u].sta) {
dis[u][1 - hole_u] = dis[u][hole_u] + h[u].sta;
q.push({u, t.t + 1, dis[u][1 - hole_u]});
}
}
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first, w = g[u][i].second;
int hole_v = ((h[v].hol + t.t + 1) & 1); // hole_v 同理
int val = calc(h[u].wei, h[v].wei, hole_u, 1 - hole_v, w); // 计算代价
if (dis[v][hole_v] > dis[u][hole_u] + val) { // 转移
dis[v][hole_v] = dis[u][hole_u] + val;
q.push({v, t.t + 1, dis[v][hole_v]});
}
}
}
}
void init() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> h[i].hol;
}
for (int i = 1; i <= n; i++) {
cin >> h[i].wei;
}
for (int i = 1; i <= n; i++) {
cin >> h[i].sta;
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
}
void solve() {
dijkstra();
cout << min(dis[n][0], dis[n][1]); // 最后可以是黑白两种
}
void main() {
init();
solve();
}
} // namespace zqh
/*
4 5
1 0 1 0
10 10 100 10
5 20 15 10
1 2 30
2 3 40
1 3 20
1 4 200
3 4 200
130
*/