自动搬运

查看原文

来自洛谷，原作者为

	寻逍遥2006 晓看天色暮看云，行也思君，坐也思君；春赏百花冬赏雪，醒也思卿，梦也思卿

搬运于2025-08-24 22:51:16，当前版本为作者最后更新于2024-01-05 17:54:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意：一天有 $S$ 个时刻。有 $Q$ 个人，其中第 $i$ 个人要从 $T_i$ 时刻开始从 $U_i$ 走到 $V_i$。对于每条边 $(A_i,B_i)$ 经过它需要 $L_i$ 的时间，它会在第 $C_i$ 个时刻关闭，这也就意味着只有在每天的前 $C_i-L_i$ 个时刻才能够走上这条路。问每个人至少需要多长的时间能够到达目的地。

首先答案必然有一个上界 $S\times n-T_i$，也就是把第一天等完，然后一天走一条边。

我们考虑一个人可能走的两种情况：

1. 在一天之内完成了整个路程。
2. 用至少两天完成了整个路程。

第二种情况

对于第二种情况，我们可以将其分解成三段：第一天，中间的若干天（可能没有），最后一天。我们逐个来考虑。

第一天

考虑路径 $U\to V$。我们可以倒过来看：初始权值为 $S$，从 $V$ 点走到 $U$ 点，经过了第 $i$ 条边，权值会变成 $\min(S,C_i)-L_i$，我们要最大化最后的权值。

这个过程类似最短路可以使用 Dijkstra 实现，以每一个点为起点跑一遍，时间复杂度 $O(nm\log m)$。由于这个图是稠密图，所以 Dijkstra 单次可以做到 $O(n^3)$。

最后一天

考虑路径 $U\to V$。这个和正常的最短路是类似的，但是只有转移权值 $\le C_i-L_i$ 才能沿着第 $i$ 条边转移。

这个也可以使用 Dijkstra 实现，以每一个点为起点跑一遍，时间复杂度 $O(nm\log m)$ 或者 $O(n^3)$。

中间的若干天

每一天都可以看作是一条和“最后一天”相同的路径，利用最后一天对应的数组来生成一张图：如果可以从 $U$ 到达 $V$，则我们加入一条 $U\to V$ 的权值为 $S$ 的边。

然后在这张图上跑 Floyd 即可，时间复杂度 $O(n^3)$。

考虑如何计算对于答案的贡献，一个很暴力的想法是枚举第一天的终点 $U'$ 和最后一天的起点 $V'$，判断第一天 $U\to U'$ 的合法性，然后把三段的贡献加到一起。但是这样单次的复杂度为 $O(n^2)$ 无法接受。

我们考虑到 $V'$ 的枚举是只与 $U'$ 和 $V_i$ 有关的，与 $U_i$ 和 $T_i$ 无关。所以我们预处理对于每一个 $U'$ 和 $V_i$ 的 $V'$ 的枚举，这样在求解的过程中只需要枚举 $U'$ 即可。单次求解时间复杂度为 $O(n)$。

第一种情况

我们考虑一条从 $T=0$ 时刻开始的，合法的从 $U$ 到 $V$ 的路径，每次必然是能走就走，我们逐渐的增大 $T$，直到某一个时刻 $T=T'+1$ 时，有一条路是不可经过的了。也就是至多在 $T'$ 时刻出发，才能够走这一条路径。我们考虑限制住这条路径的是编号为 $x$ 的边，则从 $T'$ 时刻出发，必然会在 $C_x-L_x$ 时刻到达 $A_x$ 或 $B_x$，再在 $C_x$ 时刻到达这条边的另一端。

我们考虑枚举这条边 $x$，则可以将所有这样的路径拆成两部分（假设从 $A_x$ 进入这条边，从 $B_x$ 离开这条边，反过来也是类似的）：第一部分是从 $U\to A_x$，在 $C_x-L_x$ 时刻到达 $A_x$，这个可以和第二种情况中的“第一天”类似的方式处理；第二部分是 $B_x\to V$，从 $C_x$ 时刻出发，这个可以和第二种情况中的“最后一天”类似的方式处理。

对于某一对 $U,V$，假设我们得到至多在 $T_1$ 时刻从 $U$ 出发，可以在 $T_2$ 时刻到达 $V$，则如果要走 $U\to V$，且可以在 $\le T_1$ 的时刻出发，就可以以 $T_2-T_1$ 的代价走到。

对于每一对 $U,V$，都可以得到这样的 $O(m)$ 条路径，将其按照 $T_1$ 排序，去掉所有被其他路径偏序了的路径，就可以通过一次二分来得到每一次询问能否在第一天之内到达，同时可以得到它需要消耗的最短时间。

考虑时间复杂度：对于枚举每一条边跑一次 Dijkstra，时间复杂度为 $O(mn^2)$；对于每一个 $U\to V$ 点对处理那 $O(m)$ 条路经，时间复杂度 $O(n^2m\log m)$；每一次求解答案需要一次二分，时间复杂度 $O(Q\log m)$。

总体时间复杂度为 $O(n^2m\log m+Q(n+\log m))$ 可以通过。

#include "escape_route.h"
#include <bits/stdc++.h>

using namespace std;

template<typename T>bool get_max(T &a,T b){if(a<b) return a=b,true;return false;}
template<typename T>bool get_min(T &a,T b){if(a>b) return a=b,true;return false;}

vector<long long> ans;
vector<pair<int,int> >ed[100];
vector<pair<long long,long long> >mind[100][100],tmp;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > G;
priority_queue<pair<long long,int> >G_;
long long dis[100][100],tr[100][100];

long long sid[100][100];

long long dis1[100],dis2[100];

int f[100][100];
bool vis[100];

vector<long long> calculate_necessary_time(
	int N, int M, long long S, int Q, vector<int> A, vector<int> B,
    vector<long long> L, vector<long long> C, vector<int> U,
    vector<int> V, vector<long long> T)
{
	ans.resize(Q);
	for(int i=0;i<M;i++)
		ed[A[i]].push_back(make_pair(B[i],i)),
		ed[B[i]].push_back(make_pair(A[i],i));
	
	//solve go in days

	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++) dis[i][j]=S*N,vis[j]=false;
		dis[i][i]=0;G.push(make_pair(0ll,i));
		while(!G.empty())
		{
			int v=G.top().second;G.pop();
			if(vis[v]) continue;
			vis[v]=true;
			for(pair<int,int> g:ed[v])
				if(dis[i][v]+L[g.second]<=C[g.second]&&dis[i][g.first]>dis[i][v]+L[g.second])
					G.push(make_pair(dis[i][g.first]=dis[i][v]+L[g.second],g.first));
		}
		for(int j=0;j<N;j++)
			f[i][j]=(dis[i][j]<S?1:N+1);
	}
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++) sid[i][j]=-1,vis[j]=false;
		sid[i][i]=S;G_.push(make_pair(S,i));
		while(!G_.empty())
		{
			int v=G_.top().second;G_.pop();
			if(vis[v]) continue;
			vis[v]=true;
			for(pair<int,int> g:ed[v])
				if(get_max(sid[i][g.first],min(sid[i][v],C[g.second])-L[g.second]))
					G_.push(make_pair(sid[i][g.first],g.first));
		}
	}

	for(int i=0;i<N;i++)
		f[i][i]=0;

	for(int k=0;k<N;k++)
	for(int i=0;i<N;i++)
	for(int j=0;j<N;j++)
		f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	for(int i=0;i<N;i++)
	for(int j=0;j<N;j++)
	{
		tr[i][j]=f[i][j]*S;
		for(int k=0;k<N;k++)
			tr[i][j]=min(tr[i][j],f[i][k]*S+dis[k][j]);
	}

	//solve go in one day

	for(int i=0;i<M;i++)
	{
		//A[i]->B[i]
		memset(dis1,0xcf,sizeof(dis1));
		memset(dis2,0x3f,sizeof(dis2));
		dis1[A[i]]=C[i]-L[i],dis2[B[i]]=C[i];
		memset(vis,0,sizeof(vis));
		for(int j=0,mx;j<N;j++)
		{
			mx=-1;
			for(int k=0;k<N;k++)
				if(!vis[k]&&(mx==-1||dis1[mx]<dis1[k]))
					mx=k;
			vis[mx]=true;
			for(pair<int,int> g:ed[mx])
				if(dis1[mx]<=C[g.second]&&dis1[g.first]<dis1[mx]-L[g.second])
					dis1[g.first]=dis1[mx]-L[g.second];
		}
		memset(vis,0,sizeof(vis));
		for(int j=0,mn;j<N;j++)
		{
			mn=-1;
			for(int k=0;k<N;k++)
				if(!vis[k]&&(mn==-1||dis2[mn]>dis2[k]))
					mn=k;
			vis[mn]=true;
			for(pair<int,int> g:ed[mn])
				if(dis2[mn]<=C[g.second]-L[g.second]&&dis2[g.first]>dis2[mn]+L[g.second])
					dis2[g.first]=dis2[mn]+L[g.second];
		}
		for(int x=0;x<N;x++)
		for(int y=0;y<N;y++)
			if(dis1[x]>=0&&dis2[y]<=S)
				mind[x][y].push_back(make_pair(dis1[x],dis2[y]-dis1[x]));
		
		//B[i]->A[i]
		memset(dis1,0xcf,sizeof(dis1));
		memset(dis2,0x3f,sizeof(dis2));
		dis1[B[i]]=C[i]-L[i],dis2[A[i]]=C[i];
		memset(vis,0,sizeof(vis));
		for(int j=0,mx;j<N;j++)
		{
			mx=-1;
			for(int k=0;k<N;k++)
				if(!vis[k]&&(mx==-1||dis1[mx]<dis1[k]))
					mx=k;
			vis[mx]=true;
			for(pair<int,int> g:ed[mx])
				if(dis1[mx]<=C[g.second]&&dis1[g.first]<dis1[mx]-L[g.second])
					dis1[g.first]=dis1[mx]-L[g.second];
		}
		memset(vis,0,sizeof(vis));
		for(int j=0,mn;j<N;j++)
		{
			mn=-1;
			for(int k=0;k<N;k++)
				if(!vis[k]&&(mn==-1||dis2[mn]>dis2[k]))
					mn=k;
			vis[mn]=true;
			for(pair<int,int> g:ed[mn])
				if(dis2[mn]<=C[g.second]-L[g.second]&&dis2[g.first]>dis2[mn]+L[g.second])
					dis2[g.first]=dis2[mn]+L[g.second];
		}
		for(int x=0;x<N;x++)
		for(int y=0;y<N;y++)
			if(dis1[x]>=0&&dis2[y]<=S)
				mind[x][y].push_back(make_pair(dis1[x],dis2[y]-dis1[x]));
	}

	for(int x=0;x<N;x++)
	for(int y=0;y<N;y++)
	if(mind[x][y].size())
	{
		sort(mind[x][y].begin(),mind[x][y].end(),[&](pair<long long,long long> A,pair<long long,long long> B)
		{if(A.first!=B.first) return A.first<B.first;else return A.second>B.second;});
		vector<pair<long long,long long> >().swap(tmp);
		for(pair<long long,long long> &g:mind[x][y])
		{
			while(!tmp.empty()&&tmp.rbegin()->second>g.second) tmp.pop_back();
			tmp.push_back(g);
		}
		swap(tmp,mind[x][y]);
	}

	vector<pair<long long,long long> >::iterator it;

	for(int i=0;i<Q;i++)
	{
		if((it=lower_bound(mind[U[i]][V[i]].begin(),mind[U[i]][V[i]].end(),make_pair(T[i],0ll)))!=mind[U[i]][V[i]].end())
			ans[i]=it->second;
		else ans[i]=(N+1)*S;
        
		if(T[i]<=sid[V[i]][U[i]])
			get_min(ans[i],S-sid[V[i]][U[i]]);
		
		for(int j=0;j<N;j++)
			if(T[i]<=sid[j][U[i]])
				get_min(ans[i],S-T[i]+tr[j][V[i]]);
	}
	return ans;
}

注：需要写标准输入输出，而不是 JOISC 的交互。