JOISC2021 D2T1 Escape Route

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

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

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

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

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

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

#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();
}
\