[CF843D]Dynamic Shortest Path

题目大意：

给定一个带权有向图，包含\(n(n\le10^5)\)个点和\(m(m\le10^5)\)条边。共\(q(q\le2000)\)次操作，操作包含以下两种：

\(1\:v\)——查询从\(1\)到\(v\)的最短路。
\(2\:c\:l_1\:l_2\:\ldots\:l_c\)——将边\(l_1,l_2,\ldots,l_c\)增加\(1\)的权值。

思路：

首先使用Dijkstra算法求出原图的单源最短路径\(dis[i]\)。对于所有的操作\(2\)，考虑增加边权后对答案的影响。不难发现每次修改边权后\(dis[i]\)都会增加一定量或保持不变。不妨将每次每个点的增加量记作\(add[i]\)，考虑增加边权后计算\(add[i]\)的值。

类比Dijkstra算法的“松弛”操作，对于一个结点\(x\)，若\(add[x]\ne0\)，我们可以用\(x\)来松弛别的结点。枚举\(x\)的下一个结点\(y\)，若此时用\(x\)作为最短路中的上一任结点，则最短路长度需要增加\(dis[x]+w(x,y)+add[x]-dis[y]\)。而\(add[y]\)则需要对所有这样的值取\(\min\)。这样完成所有的松弛操作后，\(dis'[i]=dis[i]+add[i]\)。而这可以用BFS实现，其中当\(add[i]>c\)时则没有“松弛”的必要，可以进行剪枝。

配对堆优化Dijkstra复杂度\(\mathcal O(n\log n+m)\)，单次BFS更新最短路\(\mathcal O(q(n+m))\)，总时间复杂度\(\mathcal O(n\log n+m+q(n+m))\)。

细节：

注意边权可能为\(0\)，因此Dijkstra中被松弛的结点可能会跑到堆顶，不能松弛完再删除堆顶元素。本题时间限制较紧，实现时注意优化常数。

源代码：

#include<queue>

#include<cstdio>

#include<cctype>

#include<climits>

#include<algorithm>

#include<functional>

#include<forward_list>

#include<ext/pb_ds/priority_queue.hpp>

using int64=long long;

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

constexpr int N=1e5+1;

int n,w[N],add[N];

int64 dis[N];

using Edge=std::pair<int,int>;

std::forward_list<Edge> e[N];

using Vertex=std::pair<int64,int>;

__gnu_pbds::priority_queue<Vertex,std::greater<Vertex>> q;

__gnu_pbds::priority_queue<Vertex,std::greater<Vertex>>::point_iterator p[N];

inline void dijkstra() {

	for(register int i=1;i<=n;i++) {

		p[i]=q.push({dis[i]=i==1?0:LLONG_MAX,i});

	}

	while(!q.empty()&&q.top().first!=LLONG_MAX) {

		const int x=q.top().second;

		q.pop();

		for(register auto &j:e[x]) {

			const int &y=j.first,&w=::w[j.second];

			if(dis[x]+w<dis[y]) {

				q.modify(p[y],{dis[y]=dis[x]+w,y});

			}

		}

	}

	q.clear();

}

std::queue<int> v[N];

int main() {

	n=getint();

	const int m=getint(),q=getint();

	for(register int i=1;i<=m;i++) {

		const int u=getint(),v=getint();

		w[i]=getint();

		e[u].emplace_front(std::make_pair(v,i));

	}

	dijkstra();

	for(register int i=1;i<=n;i++) {

		if(dis[i]==LLONG_MAX) dis[i]=-1;

	}

	for(register int i=0;i<q;i++) {

		if(getint()==1) {

			printf("%lld\n",dis[getint()]);

		} else {

			const int c=getint();

			for(register int i=0;i<c;i++) w[getint()]++;

			std::fill(&add[1],&add[n]+1,c+1);

			v[add[1]=0].emplace(1);

			for(register int i=0;i<=c;i++) {

				for(;!v[i].empty();v[i].pop()) {

					const int &x=v[i].front();

					if(add[x]!=i) continue;

					for(register auto &j:e[x]) {

						const int &y=j.first,&w=::w[j.second];

						const int64 d=dis[x]+w+add[x]-dis[y];

						if(d<add[y]) v[add[y]=d].emplace(y);

					}

				}

			}

			for(register int i=1;i<=n;i++) {

				if(add[i]!=c+1) dis[i]+=add[i];

			}

		}

	}

	return 0;

}

巴特西

[CF843D]Dynamic Shortest Path

[CF843D]Dynamic Shortest Path

题目大意：

思路：

细节：

源代码：

最新文章

热门文章