[ARC165C] Social Distance on Graph

转化题意，对图进行黑白染色，求最大的 \(X\) 满足所有 \(u, v\) 间最短路径小于 \(X\) 的 \(u, v\) 异色。

很明显是二分答案，假设现在二分到 \(mid\)，转化为判定型问题。

直接 \(n^2\) 枚举点肯定不对。

发现性质：如果 \(u,v\) 的最短路径长度小于 \(X\) 且最短路径上经过的边数大于 \(1\)，则一定无法染色。

所以对于所有由两条边组成的路径的最小值应该为二分上界 \(r\)。

确定上界后，只需考虑所有由一条边组成的最短路，即所有边权小于 \(X\) 的边拿出来进行二分图判定。

这样拿出来的边一定是最短路，否则二分上界一定比它小。

本题巧妙运用了二分上界，使得 \(\rm check\) 函数能在正确复杂度内执行。

#define int ll
typedef pair<int, int> PII;
const int N = 2e5 + 5; 
int n, m, mx[N], smx[N]; // 含义相反因为之前写成最大值了
vector <PII> E[N];
int color[N];
bool dfs(int x, int mid, int col)
{
	// cout << x << ' ' << color[x] << "!!!\n";
	if (~color[x]) return color[x] == col;
	color[x] = col;
	for (auto v : E[x])
	{
		if (v.second >= mid) continue;
		if (!dfs(v.first, mid, col ^ 1)) return 0;
	}
	return 1;
}
bool chk(int mid)
{
	R(i, 1, n) color[i] = -1;
	// cout << color[1] << '\n';
	bool res = 1; 
	R(i, 1, n) if (color[i] == -1) if (!dfs(i, mid, 0)) return false; //cout << i << ' ' <<res << endl;
	return true;
}
void solve()
{
	cin >> n >> m;
	int l = 1, r = INT_MAX;
	R(i, 1, n) mx[i] = smx[i] = INT_MAX;
	R(i, 1, m)
	{
		int u, v, w; cin >> u >> v >> w;
		E[u].pb({v, w}); E[v].pb({u, w});
		if (w < mx[u]) smx[u] = mx[u], mx[u] = w;
		else if (w < smx[u]) smx[u] = w;
		if (w < mx[v]) smx[v] = mx[v], mx[v] = w;
		else if (w < smx[v]) smx[v] = w;
	}
	R(i, 1, n) 
	{
		if (smx[i] == INT_MAX) continue;
		r = min(r, (mx[i] == INT_MAX ? 0 : mx[i]) + (smx[i] == INT_MAX ? 0 : smx[i])); 
		// cout << mx[i] << ' ' << smx[i] << endl;
		// cout << r << endl;
	}
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (chk(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << endl;
}
signed main() 
{
	int T = 1; 
	// read(T); 
	while (T--) solve();
    return 0;
}