T3
有一个 \(n\) 点 \(m\) 边的简单无向图，每个点有颜色 \(c_i\) 和点权 。
经过某个点时需要花费 \(w_i\) 的能量放下一个标记，若 \(c_i\ne c_j\) 则在 \(i\) 处可远程回收 \(j\) 处的标记，要求每刻能量非负，求对任意两点 \(x\) 到 \(y\) 的最小初始能量，若不存在输出 \(-1\)。
注意到 性质：在每一个点能回收标记就回收标记，所以一定是走上一段相同颜色的，然后换一种颜色，把先前的标记都回收了，然后再沿着当前颜色走。
第一反应：设 \(f_{i,j}\) 表示任意两点这间的 \(\min (\max(路径上一段相同颜色的距离))\)，但是这样发现很难转移。
于是：设 \(f_{i,j}\) 表示 只走同一种颜色，任意两点之间的答案，\(g_{i,j}\) 表示 不同颜色，两点间的答案，\(ans_{i,j}\) 表示两点之间的答案。
初始化：
- $f_{i,j} =w_i + w_j (c_i == c_j) $
- \(g_{i,j} = \min(f_{i,k} + w_j) (c_k\ne c_j)\) (这样可以保证转移时只涉及 \(\min,\max\) 操作，不涉及相加操作)
转移：
- \(f_{i,j} = \min(f_{i,k} + f_{k,j} - w_k)\)（需要把重复算的减去）
- \(g_{i,j} = \min(\max(g_{i,k}, g_{k,j}))\)（floyd）
- \(ans_{i,j} = min(f_{i,j}, g_{i,j}, \max(g_{i,k}, f_{k,j}))\)（可以只走相同的，也可以只走不同的，也可以在不同的后面再接一段相同的)
code
#include<bits/stdc++.h>
#define int long long
#define N 510
#define pb push_back
#define Fo(a, b) for(auto a : b)
#define fo(a, b, c) for(int b = a; b <= c; b++)
using namespace std;
int n, m, c[N], w[N], T;
int f[N][N], g[N][N], ans[N][N];
vector<int>G[N];
signed main(){//freopen("ex_graph2.in", "r", stdin);//freopen("graph.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin >> T;while(T--){cin >> n >> m;fo(1, i, n) cin >> c[i];memset(f, 0x3f, sizeof(f)); fo(1, i, n){cin >> w[i]; f[i][i] = w[i];}fo(1, i, n) G[i].clear();fo(1, i, m){int x, y; cin >> x >> y;G[x].pb(y), G[y].pb(x);if(c[x] == c[y]) f[x][y] = f[y][x] = w[x] + w[y];}fo(1, k, n) fo(1, i, n) fo(1, j, n){f[i][j] = min(f[i][k] + f[k][j] - w[k], f[i][j]);}memset(g, 0x3f, sizeof(g));fo(1, i, n) fo(1, j, n) Fo(v, G[j]){if(c[v] != c[j]) g[i][v] = min(g[i][v], f[i][j] + w[v]); }fo(1, k, n) fo(1, i, n) fo(1, j, n){g[i][j] = min(g[i][j], max(g[i][k], g[k][j]));}memset(ans, 0x3f, sizeof(ans));fo(1, i, n) fo(1, j, n){ans[i][j] = min(f[i][j], g[i][j]);fo(1, k, n) ans[i][j] = min(ans[i][j], max(g[i][k], f[k][j]));}fo(1, i, n){fo(1, j, n) cout << ans[i][j] << ' ';cout << "\n";}}return 0;
}