动态最短路题解 - 洛谷保存站

## 题意描述

维护一个动态最短路，每次加一条边，求每次加$1$到$n$的最短路。

为了简单，只需输出下面的内容：

设每次最短路为$s$，给出一个阈值$T$，当$s<T$的时候清空添加的边。

输出清空了多少次和每次清空的时间(一秒增加一个边)。

## 解题思路

首先可以想到一个暴力二分。

每次清空时二分下一个清空的点，似乎没问题？

但是如果每次都加$1,n$这条边且边权小于$T$，每次二分最短路都要跑满$nlog_2n$，二分$log_2q$，清空的次数为$q$，时间过不去。

发现二分的最短路每次都跑$nlog_2n$太浪费了。

提供一种做法，先 $1$,$2$,$4$,$8$……的尝试加这么多边最短路是否$<T$，跑到$2^m$最短路长度$<T$了，二分$[1,n]$即可。

这样显然可以通过之前的$hack$，但复杂度为什么是正确的呢？

考虑每两次清空操作，之间与$1$连通的点的数量最多是添加的边的数量，设它为$t$。

对于倍增确定值域和二分，只要最短路只走与$1$连通的点，复杂度为$tlog_2nlog_2q$的，而$t$的和最大为$q$(边的最大和)，所以复杂度为$qlog_2qlog_2n$。

## 代码

````cpp
#include<bits/stdc++.h>
#define v cout<<"!!!!!!!!!!"<<endl;
using namespace std;
struct H{
	int x,y;
	H(int x_,int y_){x=x_,y=y_;}
};
bool operator<(H x,H y){return x.y>y.y;}
int ts,bj,js,n,m,k,l,q,k4[1000007],k1[1000007],k2[1000007],k3[1000007],cd,k6[1000007],a1[1000007],a2[1000006],a3[1000007],qu[1000007],cnt,ans[1000007],t;
bool k5[1000007];
priority_queue<H> p;
void DD(int x,int y,int z){
	k1[++cd]=k2[x];
	k2[x]=cd;
	k3[cd]=y;
	k4[cd]=z;
}
void De(int x){
	for(int i=js;i>=x+1;i--){
		cd--;
		k2[a2[i]]=k1[k2[a2[i]]];
		cd--;
		k2[a1[i]]=k1[k2[a1[i]]];
	}
}
bool Dj(int y){
	if(y>q)return 0;
	if(js>y)De(y);
	else for(int i=js+1;i<=y;i++)DD(a1[i],a2[i],a3[i]),DD(a2[i],a1[i],a3[i]);
	js=y;
	p.push(H(1,0));
	k6[1]=0;
	while(!p.empty()){
		int to=p.top().x;
		p.pop();
		if(k5[to])continue;
		qu[++cnt]=to;
		k5[to]=1;
		for(int j=k2[to];j!=0;j=k1[j]){
			int tt=k3[j];
			if(k4[j]+k6[to]<k6[tt]){
				k6[tt]=k4[j]+k6[to];
				p.push(H(tt,k6[tt]));
			}
		}
	}
	
	int ss=k6[n];
	//cout<<cnt<<" "<<ss<<" "<<y<<endl;
	for(int i=1;i<=cnt;i++)k6[qu[i]]=1e9+1,k5[qu[i]]=0;
	cnt=0;
	if(ss>l)return 1;
	return 0;
}
int Ef1(int l,int r){
	int fl=l,fr=r;
	while(fl<=fr){
		int mid=(fl+fr)/2;
		if(Dj(bj+mid))fl=mid+1;
		else fr=mid-1;
		ts++;
	}
	return fl;
}
int main(){
//	freopen("path3.in","r",stdin);
//	freopen("path2.out","w",stdout);
	cin>>n>>q>>l;
	for(int i=1;i<=n;i++)k6[i]=1e9;
	for(int i=1;i<=q;i++)scanf("%d%d%d",&a1[i],&a2[i],&a3[i]);
	while(js!=q){
		int s1=0;
		while(Dj(js+(1<<s1)))s1++;
		s1++;
		ans[++t]=Ef1(1,(1<<s1))+bj;
		if(Dj(ans[t]));
		De(bj);
		bj=js;
	}
	if(ans[t]==q+1)t--;
	js=0;
	cout<<t<<'\n';
	for(int i=1;i<=t;i++)printf("%d ",ans[i]);
}

````

正在渲染内容...