JOISC2021 D2T1 Escape Route

好题。首先我们考虑一天之内能到达的情况。我们考虑对于每一对 $s,t$ 求出一个最晚的时间 $T$ ,使得在 $T$ 之前的时刻出发,都可以在当天到达 $t$ (这里要注意有可能一天之内到不了,也就是可能 $T < 0$ )。

这个东西如何计算?首先有一种非常暴力的想法,我们每次加入一个当前连通块连出去的边,同时可能导致 $T$ 减小,然后重新跑一次最短路。考虑这样的复杂度,枚举点 $O(n)$ ,加边次数是 $O(n^2)$ ,每次跑最短路使用 dijkstra (这里显然 $O(n^2+m)$ 是优于 $O(m\log m)$ 的),复杂度就是 $O(n^5)$ 。看起来不太能跑过。

但是这提示我们可以去枚举那个卡着上界的边 $(u,v,l,c)$ ,因为 $T$ 必然是由中间某个边的关闭时间决定的。然后尝试用这条边来卡上界,具体来说求出 $u$ 开始时间为 $c-l$ ,反着走图,到达 $s$ 所需要的最小时间,以及求出 $v$ 开始时间为 $c$ ,走正图,到达 $t$ 所需的最小时间,这两个值可以用类 dijkstra 来做,复杂度 $O(n^2)$ ,由这两个值来更新最晚时间,同时也就得到了在某个时间之前从 $s$ 到 $t$ 的一条可能的最短路。这部分的复杂度 $O(n^4)$ 。

于是对所有卡上界的边都求出某个时间之前从 $s$ 到 $t$ 的一个可能的最短路后按出发时间最晚值排序后求一个后缀最小值,于是就可以通过在这里面 lower_bound 得到当天到达的时间。

然后考虑如何做在非当天走到的情况。不妨枚举一下第一天走到哪个点,于是问题就变成了从某个点出发,且时间为 $0$ ,到达另一个点的最短路径。不难发现这个东西必然是先走几个整天,然后最后再走某一天的一个前缀。我们不妨设 $dis[u][v]$ 为 $u$ 在出发时间为 $0$ 时一天内到达 $v$ 的最短路,如果到不了则是 $\infin$ 。这个东西可以和刚刚一样的用类 dijkstra 来做。然后我们建一个新图,把一天内能到达的两点 $u \to v$ 连一条权值为 $1$ 的边,于是两点在这个图上的最短路就是需要花费多少个整天,跑一次 Floyd 即可。于是我们就可以对任意一对 $u,v$ 求出出发时间为 $0$ 的时候的最短路了,具体来说我们枚举一个点 $k$ ,表示从 $u \to k$ 走整天,最后从 $k \to v$ 走一天的一段前缀。这部分复杂度 $O(n^3)$ 。

于是这道题就做完了。复杂度 $O(n^4 + nq)$ 。代码常数非常大,跑了 8.3s 。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "cassert"
#include "queue"
using namespace std;
#define MAXN 93
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , q;
ll s;
int A[MAXN];

ll L[MAXN][MAXN] , C[MAXN][MAXN];
ll W[MAXN][MAXN][2][MAXN];
ll dis[MAXN][MAXN];

int vis[MAXN];
void dijk( int s , ll cur , ll ds[MAXN] ) {
rep( i , 1 , n ) vis[i] = 0 , ds[i] = 1e18;
ds[s] = 0;
while( 233 ) {
pair<ll,int> mn = mp( 1e18 , 0 );
rep( i , 1 , n ) if( !vis[i] ) mn = min( mn , mp( ds[i] , i ) );
if( !mn.se ) return;
int u = mn.se;
vis[u] = 1;
rep( v , 1 , n ) if( !vis[v] && C[u][v] - L[u][v] >= cur + ds[u] && ds[u] + L[u][v] < ds[v] )
ds[v] = ds[u] + L[u][v];
}
}

void dijk2( int s , ll cur , ll ds[MAXN] ) {
rep( i , 1 , n ) vis[i] = 0 , ds[i] = 1e18;
ds[s] = 0;
while( 233 ) {
pair<ll,int> mn = mp( 1e18 , 0 );
rep( i , 1 , n ) if( !vis[i] ) mn = min( mn , mp( ds[i] , i ) );
if( !mn.se ) return;
int u = mn.se;
vis[u] = 1;
rep( v , 1 , n ) if( !vis[v] && C[v][u] >= cur - ds[u] && ds[u] + L[v][u] < ds[v] )
ds[v] = ds[u] + L[v][u];
}
}

ll lt[MAXN][MAXN];
vector<pair<ll,ll>> D[MAXN][MAXN];

int G[MAXN][MAXN];
ll ar[MAXN][MAXN];

void solve() {
cin >> n >> m >> s >> q;
memset( L , 0x3f , sizeof L );
rep( i , 1 , m ) {
int u , v;
ll l , c;
scanf("%d%d%lld%lld",&u,&v,&l,&c);
++ u , ++ v;
L[u][v] = L[v][u] = l , C[u][v] = C[v][u] = c;
}
memset( lt , -1 , sizeof lt );
rep( u , 1 , n ) lt[u][u] = s;
rep( u , 1 , n ) rep( v , 1 , n ) if( L[u][v] < 1e18 )
dijk( u , C[u][v] , W[u][v][1] ) , dijk2( u , C[u][v] - L[u][v] , W[u][v][0] );
rep( u , 1 , n ) rep( v , 1 , n ) {
rep( s , 1 , n ) rep( t , 1 , n ) if( L[s][t] < 1e18 ) {
ll ds = W[s][t][0][u] + L[s][t] + W[t][s][1][v] , tim = C[s][t] - L[s][t] - W[s][t][0][u];
if( ds < 1e18 ) {
lt[u][v] = max( lt[u][v] , tim );
D[u][v].eb( mp( tim , ds ) );
}
}
sort( all( D[u][v] ) );
int s = D[u][v].size() - 1;
per( i , s - 1 , 0 ) D[u][v][i].se = min( D[u][v][i].se , D[u][v][i + 1].se );
}
memset( G , 0x3f , sizeof G );
rep( u , 1 , n ) {
G[u][u] = 0;
dijk( u , 0 , dis[u] );
rep( v , 1 , n ) if( u != v && dis[u][v] < 1e18 ) G[u][v] = 1;
}
rep( k , 1 , n ) rep( i , 1 , n ) rep( j , 1 , n )
G[i][j] = min( G[i][j] , G[i][k] + G[k][j] );
memset( ar , 0x3f , sizeof ar );
rep( u , 1 , n ) rep( v , 1 , n ) {
ar[u][v] = dis[u][v];
rep( k , 1 , n ) if( dis[k][v] < 1e18 )
ar[u][v] = min( ar[u][v] , G[u][k] * s + dis[k][v] );
}
rep( i , 1 , q ) {
int u , v; ll t;
scanf("%d%d%lld",&u,&v,&t);
++ u , ++ v;
if( lt[u][v] >= t ) {
printf("%lld\n",lower_bound( all( D[u][v] ) , mp( t , 0ll ) ) -> se);
} else {
ll as = 1e18;
rep( k , 1 , n ) if( lt[u][k] >= t )
as = min( as , s - t + ar[k][v] );
printf("%lld\n",as);
}
}

}

signed main() {
// freopen("input.txt","r",stdin) , freopen("ot","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2021/04/19/joisc2021-d2t1-escape-route/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog