专栏文章

P11336题解

aallenchoi
P11336题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miq05q6k
此快照首次捕获于
2025/12/03 20:47
3 个月前
此快照最后确认于
2025/12/03 20:47
3 个月前
查看原文

科技：

Dijkstra，最短路树

思路：

首先，以 11 号点为起点跑最短路，求出最短路树。
设操作的两条边编号为 a,b(a<b)a,b(a<b)，则 bb 是 [a+1,m][a+1,m] 中边权最大的那条边。
假如 aa 不在树上 11 到 nn 的路径上，此时的最短路就是原来的 dis1,ndis_{1,n}；否则，最短路可能是 dis1,n+wbdis_{1,n}+w_b，也可能是经过一条非树边 (x,y)(x,y) 的路径，如下图：

其中标黄的蓝边是 aa 边。
这种情况的最短路是 dis1,x+wx,y+disn,ydis_{1,x}+w_{x,y}+dis_{n,y}，证明如下：
首先，由于点 xx 一定在 uu 的子树以外，所以 11 到 xx 的最短路即树上路径必然不经过 (u,v)(u,v)；
接下来考虑 disn,ydis_{n,y} 对应的路径。
考虑反证法，假设该路径经过了 (u,v)(u,v)，那么这条路径形如 y,...u,v,...ny,...u,v,...n。注意到点 yy 是在 vv 的子树内的，所以 vv 是 yy 的祖先，那么 yy 到 vv 的最短路径就是树上的路径（考虑 Dijkstra 从 vv 到 yy 增广的过程），必然不经过点 uu，因此比上面的那条路径更优。由此得出，disn,ydis_{n,y} 对应的路径也不经过 (u,v)(u,v)。
证毕。
考虑怎么计算答案。
我们称树上 11 到 nn 的路径上的点为关键点，设 x,yx,y 最深的关键点祖先分别为 i,ji,j（见上图），那么 dis1,x+wx,y+disn,ydis_{1,x}+w_{x,y}+dis_{n,y} 可以作为 aa 是 i,ji,j 之间的边时的答案。
于是可以离线处理。维护一个可重集，从上到下枚举关键点、关键边。枚举所有非树边 (x,y)(x,y)，设它对应的最短路长度为 vv，我们在 ii 的时候将 vv 加入 ss，在 jj 的时候删除，那么一条关键边的答案就是 min⁡(dis1,n+wb,min⁡v∈sv)\min(dis_{1,n}+w_b,\min\limits_{v\in s}v)，最终答案就是这串东西的 max⁡\max。
我们只用跑两次最短路，做 O(m)O(m) 次 multiset 操作，所以时间复杂度单 log⁡\log。
可能评个蓝或紫？

代码：

CPP
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
const ll INF = 1e18;
int n,m,tot = 1,top,head[N],to[N << 1],val[N << 1],nxt[N << 1],vis[N << 1],w[N],p[N],id[N],h[N];
ll ans,dis[2][N];
vector <ll> v1[N],v2[N];
multiset <ll> s;
struct Node{int x,pre;ll d;};
bool operator < (Node x,Node y){return x.d > y.d;}
priority_queue <Node> q;
void add_(int x,int y,int z)
{
	to[++tot] = y,val[tot] = z;
	nxt[tot] = head[x],head[x] = tot;
}
void dijkstra(int s,int t)
{
	memset(dis[t],127,sizeof(dis[t]));
	dis[t][s] = 0,q.push((Node){s,0,0});
	while(!q.empty())
	{
		Node tmp = q.top();
		q.pop();
		int x = tmp.x,pre = tmp.pre;
		ll d = tmp.d;
		if(d > dis[t][x]) continue;
		vis[pre] = t;
		for(int i = head[x],y;i;i = nxt[i])
		{
			y = to[i];
			if(d + val[i] < dis[t][y])
			{
				dis[t][y] = d + val[i];
				q.push((Node){y,i,d + val[i]});
			}
		}
	}
}
bool dfs1(int x)
{
	p[++top] = x,h[x] = top;
	if(x == n) return true;
	for(int i = head[x],y;i;i = nxt[i])
	{
		y = to[i];
		if(!vis[i]) continue;
		id[top] = i / 2;
		if(dfs1(y)) return true;
	}
	top--,h[x] = 0;
	return false;
}
void dfs2(int x)
{
	for(int i = head[x],y;i;i = nxt[i])
	{
		y = to[i];
		if(!vis[i]) continue;
		if(!h[y]) h[y] = h[x];
		dfs2(y);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1,a,b,c;i <= m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		add_(a,b,c),add_(b,a,c);
		w[i] = c;
	}
	for(int i = m;i >= 1;i--) w[i] = max(w[i],w[i + 1]);
	dijkstra(n,0),dijkstra(1,1);
	dfs1(1),dfs2(1);
	for(int i = 1;i <= n;i++)
		for(int j = head[i];j;j = nxt[j])
			if(!vis[j] && h[i] < h[to[j]])
			{
				ll tmp = dis[1][i] + dis[0][to[j]] + val[j];
				v1[h[i]].pb(tmp),v2[h[to[j]]].pb(tmp);
			}
	for(int i = 1;i < top;i++)
	{
		for(ll v : v1[i]) s.insert(v);
		for(ll v : v2[i]) s.erase(s.lower_bound(v));
		ans = max(ans,min(dis[1][n] + w[id[i] + 1],s.empty() ? INF : (*s.begin())));
	}
	printf("%lld\n",ans);
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...