P10053 题解
寻逍遥2006
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))$ 可以通过。
```cpp
#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 的交互。