JOISC 2021 逃生路线 题解

First Post:

Last Update:

我感觉我不会这种题挺正常的。比较优美的题。

首先看到题面之后容易发现 ，且只经过一天时的问题比较简单，只需以该点为源点跑一遍 Dijkstra 算法，每次用 松弛 时判断 是否不超过 即可。

这启示我们天数其实不是很重要，运用上面的过程，我们很容易求出从点 ，在时刻 出发，能否在一天内到达点 。对这个数组跑遍 floyd 就能求出从 到 最少需要多少个整天。进一步地，从 点，在时刻 出发，到任意点 的最短时间都是好求的，枚举一个中转点 ，从 到 是若干个整天，从 到 在一天内，直接更新数组即可。

那么对于一个询问 ，我们枚举 第一天到达的最后一个点 ，那这个询问相当于被拆成 个询问，即：从点 ，时刻 出发，到达 的最少花费时间。

我一开始想着每个点维护个关于时间的分段函数，然后按时间转移来转移去什么的，这种思路其实是不可做的。

正确的做法其实是先直接考虑 到终点 的一条最短路，那么对这条路径来说，如果开始时间 （其中 在最短路上），那么这条路径就可以直接更新答案。对于 更大的情况，把取到 的那条瓶颈边删掉，继续跑最短路，就能得到一个 的做法。

考虑优化，可以直接枚举那条瓶颈边 ，钦定其刚好卡住限制，然后向起点和终点方向各跑一遍最短路，存下结果，分别设为 和 。然后枚举起点 ，这样就知道了开始时间 ，即 到的最短路。将 与 形成的二元组按照开始时间从小到大排序。然后按时间从大到小扫描每个询问，设 表示从 出发走到 ，在一天时间内的最短路，开始时间是当前询问时间。那么在扫描的过程中，对于开始时间大于等于当前询问时间的二元组 ，枚举终点 ，将 与 取 即可。维护好 后，解答询问也是简单的。

于是本题就做完了，时间复杂度 。

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;

const int N = 95,M = N * N,Ts = N * N * N;
const int MaxQ = 3e6 + 5;
typedef long long ll;
int n,m,Q;
ll e[N][N],Lim[N][N],dis1[N][N],dis2[N][N],dis3[N][N],dis4[N][N];
ll S;

ll dsx[M][N],dsy[M][N];

bool vst[N];

// dis1: 从 u 出发，时刻 0 ，走小于一天，走到点 v 的最短路
// dis2: 从 u 出发，时刻 0 ，走到 v 所需最短天数
void Dijx(int st,ll dst,ll *dis) { // 从后往前跑
	for(int i = 1;i <= n;i++) dis[i] = -1,vst[i] = 0;
	dis[st] = dst;
	for(int i = 1;i <= n;i++) {
		int k = 0;
		for(int j = 1;j <= n;j++)
			if(!vst[j] && (!k || dis[j] > dis[k])) k = j;
		if(!k) break;
		vst[k] = true;
		for(int j = 1;j <= n;j++)
			if(dis[k] <= Lim[j][k] && dis[j] < dis[k] - e[j][k])
				dis[j] = dis[k] - e[j][k];
	}
}
void Dijy(int st,ll dst,ll *dis) {
	for(int i = 1;i <= n;i++) dis[i] = 1e18,vst[i] = 0;
	dis[st] = dst;
	for(int i = 1;i <= n;i++) {
		int k = 0;
		for(int j = 1;j <= n;j++)
			if(!vst[j] && (!k || dis[j] < dis[k])) k = j;
		if(!k) break;
		vst[k] = true;
		for(int j = 1;j <= n;j++)
			if(dis[k] + e[k][j] <= Lim[k][j] && dis[j] > dis[k] + e[k][j])
				dis[j] = dis[k] + e[k][j];
	}
}

int ecnt,tcnt;
struct Node {
	int st,eid;ll tim;
	Node(){}
	Node(const int _st,const int _eid,const ll _tim):
		st(_st),eid(_eid),tim(_tim){}
	bool operator < (const Node &rhs) const { return tim < rhs.tim;}
};
Node ts[Ts]; // 存下所有开始时间的状态
void Init() {
	memset(dis1,0x3f,sizeof dis1);
	memset(dis2,0x3f,sizeof dis2);
	memset(dis3,0x3f,sizeof dis3);
	memset(dis4,0x3f,sizeof dis4);
	for(int x = 1;x <= n;x++)
		for(int y = 1;y <= n;y++)
			if(Lim[x][y]) { // 枚举瓶颈路
				++ecnt;
				Dijx(x,Lim[x][y] - e[x][y],dsx[ecnt]);
				Dijy(y,Lim[x][y],dsy[ecnt]);
				for(int u = 1;u <= n;u++) if(dsx[ecnt][u] >= 0) {
					ts[++tcnt] = Node(u,ecnt,dsx[ecnt][u]);
					for(int v = 1;v <= n;v++) if(dsy[ecnt][v] < S)
						dis1[u][v] = min(dis1[u][v],dsy[ecnt][v] - dsx[ecnt][u]),dis2[u][v] = 1;
				}
			}
	for(int i = 1;i <= n;i++) dis1[i][i] = dis2[i][i] = dis3[i][i] = dis4[i][i] = 0;
	for(int k = 1;k <= n;k++)
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				dis2[i][j] = min(dis2[i][j],dis2[i][k] + dis2[k][j]);
	for(int i = 1;i <= n;i++)
		for(int k = 1;k <= n;k++)
			for(int j = 1;j <= n;j++)
				if(dis2[i][k] <= n && dis1[k][j] < S)
					dis3[i][j] = min(dis3[i][j],dis2[i][k] * S + dis1[k][j]);
}
void Upd(int st,int eid) {
	for(int v = 1;v <= n;v++)
		if(dsy[eid][v] < S)
			dis4[st][v] = min(dis4[st][v],dsy[eid][v] - dsx[eid][st]); // 这个式子其实就是文中的 d1 + d2，需要结合 dijkstra 那一部分的代码进行理解
}

ll Qry(int u,int v,ll t) {
	if(dis4[u][v] + t < S) return dis4[u][v];
	ll res = LONG_LONG_MAX;
	for(int i = 1;i <= n;i++)
		if(dis4[u][i] < S)
		res = min(res,dis3[i][v]);
	return res + S - t;
}
int qu[MaxQ],qv[MaxQ];
ll qt[MaxQ],ans[MaxQ];
int srt[MaxQ];

int main() {
	read(n);read(m);read(S);read(Q);
	memset(e,0x3f,sizeof e);
	for(int i = 1,x,y;i <= m;i++)
		read(x),read(y),++x,++y,read(e[x][y]),read(Lim[x][y]),e[y][x] = e[x][y],Lim[y][x] = Lim[x][y];
	Init();
	for(int i = 1;i <= Q;i++)
		read(qu[i]),read(qv[i]),++qu[i],++qv[i],read(qt[i]),srt[i] = i;
	sort(srt + 1,srt + Q + 1,[&](const int &x,const int &y) { return qt[x] < qt[y];});
	sort(ts + 1,ts + tcnt + 1);
	for(int i = tcnt,j = Q;j >= 1;j--) {
		while(i >= 1 && ts[i].tim >= qt[srt[j]])
			Upd(ts[i].st,ts[i].eid),--i;
		ans[srt[j]] = Qry(qu[srt[j]],qv[srt[j]],qt[srt[j]]);
	}
	for(int i = 1;i <= Q;i++)
		write(ans[i]);
	return 0;
}
≡