补题链接

• T830128 无声竞价（auction）
• T830129 回文片段（palindrome）
• T830131 向阳方阵（sunflower）
• T830132 逐级采集（collect）
• T830134 均值达标（average）
• T830135 线路通票（pass）

讲题录屏

录制：CSP-J&S模拟赛第4场

日期：2026-10-06 19:04:20

录制文件：https://meeting.tencent.com/crm/2aPok39a7e

访问密码：89PS

T1 无声竞价（auction）

简要题意

按提交顺序给出N名参与者的姓名和报价（1≤N≤100，报价1至1999，姓名为至多20个英文字母且互异）。输出最高报价者的姓名；若最高价并列，选择最早提交的参与者。

一句话题解

仅当前报价严格大于已见最高价才更新姓名，O(N)。按>=更新的后到优先策略在唯一最大值组合法得40分。

完整题解

满分做法与正确性

按输入顺序扫描，用 best 记录已读报价中的最大值，用 ans 记录其中最早提交者。只有新报价严格大于 best 时才更新二者；报价相等时保持原人选。

初始未读记录，最高价设为 $0$，低于所有合法报价。每次读入后，上述两个变量仍分别满足“已读最大报价”和“最早达到该报价者”。读完全部参与者后便得到题目要求的姓名。

时间复杂度 $O(N)$，仅需常数个字符串与整数。全局数组并非必要：该题读到新记录后就可以直接处理。

满分参考实现

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, best = 0;
	string ans;
	cin >> n;
	while (n --) {
		string s;
		int x;
		cin >> s >> x;
		if (x > best) best = x, ans = s;
	}
	cout << ans << "\n";
	return 0;
}

T2 回文片段（palindrome）

简要题意

输入至多10组非空小写字符串，每串长度不超过10000、同文件总长度不超过20000。只能删除开头及末尾的一些字符，求留下的连续回文片段的最大长度，每组输出一个整数。

一句话题解

以每个字符或相邻字符缝为中心同时向两侧扩展，O(N²)时间O(N)空间

完整题解

枚举回文中心

一个非空回文片段的中心只有两种可能：某个字符，或两个相邻字符之间的缝。前一种对应奇数长度，后一种对应偶数长度。

枚举这两类中心，令左右指针同时向外移动。只要两端仍在字符串内且字符相同，当前片段就是回文串，可以更新答案；一旦字符不同，继续围绕同一中心扩张也不可能消除这个不相等对，因此可以立即停止。

任意合法回文片段都有上述唯一中心。扫描该中心时，在到达片段两端之前不会遇到不匹配，因而一定会访问它。算法更新的每个片段又都满足回文定义，因此最大值正确。

中心数为 $O(N)$，每个中心至多扩展 $O(N)$ 次，总时间 $O(N^2)$，存储原串需要 $O(N)$ 空间。不要求学习 Manacher 等更高级算法。

常见错误

abba 的答案是 $4$，只枚举单字符中心会漏掉它；aba 的答案是 $3$，只枚举缝隙中心也不够。bbbab 的最长回文子序列长 $4$，但最长连续回文片段仅长 $3$，不能跨过中间字符拼接。banana 的最优片段从第二个字符开始，不一定是原串的前缀。

满分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
char s[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> (s + 1);
		int n = strlen(s + 1), ans = 1;
		for (int i = 1; i <= n; i ++) {
			for (int l = i, r = i; l >= 1 && r <= n && s[l] == s[r]; l --, r ++) ans = max(ans, r - l + 1);
			for (int l = i, r = i + 1; l >= 1 && r <= n && s[l] == s[r]; l --, r ++) ans = max(ans, r - l + 1);
		}
		cout << ans << "\n";
	}
	return 0;
}

T3 向阳方阵（sunflower）

简要题意

输入至多10个N×N的方阵（2≤N≤100，同文件ΣN²≤100000，元素1至10^9），保证每个方阵由某个每行从左到右、每列从上到下均严格递增的原方阵旋转整倍90度得到。输出恢复后的原方阵。

一句话题解

四种朝向中仅一种每行每列递增

完整题解

如何确定正确朝向

原矩阵每行、每列都严格递增，所以左上角比它的右邻和下邻都小。旋转 $90$ 或 $270$ 度后，这两个方向中恰有一个反向；旋转 $180$ 度后两个方向都反向。因此，在保证输入合法的前提下，仅比较左上角、右邻和下邻就足以判断当前朝向是否正确。

如果方向不正确，就顺时针旋转一次，最多旋转三次即可。坐标映射为：原位置 $(i,j)$ 转到 $(j,N+1-i)$。必须先写入另一个数组，再整体拷贝回来，不能直接覆盖仍未使用的输入元素。

四种朝向恰好对应全部合法旋转。上述判断仅在原朝向成立，所以停下时恢复了原始布局。每次旋转 $O(N^2)$，总共至多三次，故时间复杂度 $O(N^2)$、空间复杂度 $O(N^2)$。也可以直接枚举四种坐标公式，并检查所有相邻行列关系，仍为满分复杂度。

部分分路线

• 测试点 $1\sim6$ 不需要旋转，原样输出即可得到 $30$ 分。
• 测试点 $1\sim12$ 只可能是 $0$ 或 $180$ 度。若左上角小于右下角，保持原样；否则同时反转行序与列序，得到 $60$ 分。

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, a[N][N], b[N][N], c[N * N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T; cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) cin >> a[i][j];
		for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) b[i][j] = a[i][j];
		for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) cout << b[i][j] << (j == n ? '\n' : ' ');
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, a[N][N], b[N][N], c[N * N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T; cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) cin >> a[i][j];
		bool rev = a[1][1] > a[n][n];
		for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) b[i][j] = rev ? a[n + 1 - i][n + 1 - j] : a[i][j];
		for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) cout << b[i][j] << (j == n ? '\n' : ' ');
	}
	return 0;
}

常见错误

转置或镜像不是旋转。即使转置后的矩阵也可能行列递增，它并非原矩阵的一个允许旋转，不能据此输出。把全部元素排序再按行填入也会改变原来各元素的邻接关系；例如 $\begin{pmatrix}1&5\\3&7\end{pmatrix}$ 已是合法原矩阵，不能改成 $\begin{pmatrix}1&3\\5&7\end{pmatrix}$。不同对角位置允许相等，不能在读题时额外假设全部数值互异。

满分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, a[N][N], b[N][N];
void rotate_grid() {
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++) b[j][n + 1 - i] = a[i][j];
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++) a[i][j] = b[i][j];
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= n; j ++) cin >> a[i][j];
		while (a[1][1] > a[1][2] || a[1][1] > a[2][1]) rotate_grid();
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= n; j ++) cout << a[i][j] << (j == n ? '\n' : ' ');
	}
	return 0;
}

T4 逐级采集（collect）

简要题意

在 $H\times W$ 网格上，从 S 出发四邻接移动，避开 X。有等级分别为1到 $K$ 的唯一采集点，机器人初始等级1，每采集一次升一级，只能采集不高于自身等级的点，但任何采集点都可以经过。保证全部可采集，求最短总时间。每组 $H,W\le1000$、$K\le9$，至多10组，$\sum HW\le2\times10^6$。

一句话题解

先确定采集顺序必为1到 $K$，再把相邻目标之间的最短距离分别用 BFS 求出并累加。

完整题解

为什么采集顺序唯一

初始等级为1，唯一能采集的是1号点。采集完1号点后等级为2，此时1号已用过，唯一能新采集的是2号点。依此归纳，完整采集顺序只能是1、2、……、$K$。

“可以经过”不等于“可以采集”。搜索行走路线时，所有数字格都视为空地；等级只约束是否采集，不约束通行。

30 分：没有障碍

无障碍时，两格间的最短距离是曼哈顿距离 $|x_1-x_2|+|y_1-y_2|$。按 S、1、2、……、$K$ 的顺序把相邻距离相加即可，读入后计算 $O(K)$，总时间 $O(HW+K)$。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e6 + 10;
int h, w, k, x[10], y[10], d[N][N], q[M];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char a[N][N];
int bfs(int u, int v) {
	for (int i = 1; i <= h; i ++) fill(d[i] + 1, d[i] + w + 1, -1);
	int hh = 0, tt = 0;
	q[tt ++] = x[u] * N + y[u];
	d[x[u]][y[u]] = 0;
	while (hh < tt) {
		int t = q[hh ++], px = t / N, py = t % N;
		if (px == x[v] && py == y[v]) return d[px][py];
		for (int i = 0; i < 4; i ++) {
			int nx = px + dx[i], ny = py + dy[i];
			if (nx < 1 || nx > h || ny < 1 || ny > w) continue;
			if (a[nx][ny] == 'X' || d[nx][ny] != -1) continue;
			d[nx][ny] = d[px][py] + 1;
			q[tt ++] = nx * N + ny;
		}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> h >> w >> k;
		for (int i = 1; i <= h; i ++) {
			cin >> (a[i] + 1);
			for (int j = 1; j <= w; j ++) {
				int v = -1;
				if (a[i][j] == 'S') v = 0;
				if (a[i][j] >= '1' && a[i][j] <= '9') v = a[i][j] - '0';
				if (v >= 0) x[v] = i, y[v] = j;
			}
		}
		int ans = 0;
		for (int i = 1; i <= k; i ++) ans += abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);
		cout << ans << "\n";
	}
	return 0;
}

60 分：小图上的朴素最短路

在无障碍情况下沿用上一种公式；有障碍且 $HW\le120$ 时，把每个可行走格子作为图上的点，相邻可走格子连一条单位边，分别求各段最短路。

一种容易直接实现的版本是朴素 Dijkstra：每次扫描所有格子，选择尚未确定距离且暂定距离最小的格子，再更新它的四个邻格。每段最多确定 $HW$ 个格子，每次扫描 $HW$ 个格子，总时间 $O(K(HW)^2)$，全局距离与访问数组仅需 $O(HW)$ 空间。它不是用小数组强行拒绝大图，而是大图上真实扫描次数过多。

小图也可以用 Floyd 求全源最短路，再相加。本题给出的60分参考代码采用空间更省的朴素 Dijkstra。

如果只扫描已发现但尚未确定距离的格子，在单格宽走廊中确实可能很快；但开阔区域和宽分区会同时出现大量候选格子，反复扫描仍不能保证满分范围的效率。把距离改为一维数组只能改善常数，不能代替下一节的队列 BFS。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e6 + 10;
int h, w, k, x[10], y[10], d[N][N], q[M];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char a[N][N];
bool vis[N][N];
int bfs(int u, int v) {
	for (int i = 1; i <= h; i ++) fill(d[i] + 1, d[i] + w + 1, -1);
	for (int i = 1; i <= h; i ++) fill(vis[i] + 1, vis[i] + w + 1, false);
	d[x[u]][y[u]] = 0;
	for (int t = 1; t <= h * w; t ++) {
		int px = 0, py = 0, best = 1e9;
		for (int i = 1; i <= h; i ++)
			for (int j = 1; j <= w; j ++)
				if (!vis[i][j] && d[i][j] != -1 && d[i][j] < best) best = d[i][j], px = i, py = j;
		if (!px) break;
		if (px == x[v] && py == y[v]) return best;
		vis[px][py] = true;
		for (int i = 0; i < 4; i ++) {
			int nx = px + dx[i], ny = py + dy[i];
			if (nx < 1 || nx > h || ny < 1 || ny > w || a[nx][ny] == 'X') continue;
			if (d[nx][ny] == -1 || d[nx][ny] > best + 1) d[nx][ny] = best + 1;
		}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> h >> w >> k;
		for (int i = 1; i <= h; i ++) {
			cin >> (a[i] + 1);
			for (int j = 1; j <= w; j ++) {
				int v = -1;
				if (a[i][j] == 'S') v = 0;
				if (a[i][j] >= '1' && a[i][j] <= '9') v = a[i][j] - '0';
				if (v >= 0) x[v] = i, y[v] = j;
			}
		}
		bool wall = false;
		for (int i = 1; i <= h; i ++)
			for (int j = 1; j <= w; j ++) if (a[i][j] == 'X') wall = true;
		int ans = 0;
		for (int i = 1; i <= k; i ++) ans += wall ? bfs(i - 1, i) : abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);
		cout << ans << "\n";
	}
	return 0;
}

100 分：每段使用 BFS

所有移动的代价都是1，所以从当前目标出发用 BFS，第一次到达下一目标时就得到该段最短距离。依次处理 S 到1、1到2、……、$K-1$ 到 $K$，每次重新清空距离数组。

一次 BFS 每格最多入队一次，每格检查四条可能的边，时间 $O(HW)$，总时间 $O(KHW)$，空间 $O(HW)$。

正确性证明

设各个目标依次为 $p_0=S,p_1,\ldots,p_K$。任何合法完整行动方案都必须按顺序采集这些点，它在 $p_{i-1}$ 与 $p_i$ 之间的移动次数不小于图上的最短距离 $d(p_{i-1},p_i)$，因此答案至少是这些距离之和。

反过来，对每一段选取一条最短路径并拼接。在通往 $p_i$ 的路径上可能提前经过更高等级的采集点，但题目允许仅经过而不采集；不会破坏后续方案。到达 $p_i$ 后采集并升一级，便可继续下一段。拼接方案合法且总长度恰为下界，因此下界可达。

常见错误与赛时路线

不能总从 S 计算到每个目标的距离。例如一行 S12 的正确答案为2，而分别计算 S 到1和2再求和得到3。也不能每次采集最近目标：一行 S21 中必须先经过2到达1，再返回2，答案为3；先取近处2是非法的。这个例子也说明不能把尚未解锁的采集点当作墙。

有障碍时直接套曼哈顿距离会漏掉绕路。不同段的搜索起点改变，不能沿用上一段的访问标记。答案最多是 $K(HW-1)$，在本题范围内32位有符号整数足够。

赛时先识别唯一采集次序即可迅速获得无障碍30分；能写小图最短路再拿到60分；将单位权图的搜索替换为 BFS 即可满分。位置与已采集数量组成状态的一次 BFS 也是正确的满分路线，并非错误做法。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e6 + 10;
int h, w, k, x[10], y[10], d[N][N], q[M];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char a[N][N];
int bfs(int u, int v) {
	for (int i = 1; i <= h; i ++) fill(d[i] + 1, d[i] + w + 1, -1);
	int hh = 0, tt = 0;
	q[tt ++] = x[u] * N + y[u];
	d[x[u]][y[u]] = 0;
	while (hh < tt) {
		int t = q[hh ++], px = t / N, py = t % N;
		if (px == x[v] && py == y[v]) return d[px][py];
		for (int i = 0; i < 4; i ++) {
			int nx = px + dx[i], ny = py + dy[i];
			if (nx < 1 || nx > h || ny < 1 || ny > w) continue;
			if (a[nx][ny] == 'X' || d[nx][ny] != -1) continue;
			d[nx][ny] = d[px][py] + 1;
			q[tt ++] = nx * N + ny;
		}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> h >> w >> k;
		for (int i = 1; i <= h; i ++) {
			cin >> (a[i] + 1);
			for (int j = 1; j <= w; j ++) {
				int v = -1;
				if (a[i][j] == 'S') v = 0;
				if (a[i][j] >= '1' && a[i][j] <= '9') v = a[i][j] - '0';
				if (v >= 0) x[v] = i, y[v] = j;
			}
		}
		int ans = 0;
		for (int i = 1; i <= k; i ++) ans += bfs(i - 1, i);
		cout << ans << "\n";
	}
	return 0;
}

T5 均值达标（average）

简要题意

每组给定 $N\le10^6$ 个非负整数 $A_i$ 和阈值 $P$，其中 $A_i,P\le10^9$，求平均值不小于 $P$ 的非空连续子数组数。每文件至多10组，所有 $N$ 之和不超过 $2\times10^6$，输出64位整数计数。

一句话题解

每个数减去阈值后做前缀和，按位置顺序统计此前不大于当前前缀和的个数。

完整题解

30 分：枚举连续区间

固定左端点 $l$，从左到右扩展右端点 $r$，维护区间和。若区间和不小于 $P(r-l+1)$，答案加一。

每个非空连续区间由一对端点唯一决定，因此逐对检查不重不漏。时间 $O(N^2)$，除输入数组外只需常数额外空间，适合 $N\le10000$。比较时必须先转为64位再计算 $P\times$ 长度。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, p, a[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		cin >> p;
		LL ans = 0;
		for (int l = 1; l <= n; l ++) {
			LL sum = 0;
			for (int r = l; r <= n; r ++) {
				sum += a[r];
				if (sum >= (LL)p * (r - l + 1)) ans ++;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

100 分：将平均值约束转化为序对

原条件为

$$\frac{\sum_{i=l}^{r}A_i}{r-l+1}\ge P.$$

分母为正，移项得到

$$\sum_{i=l}^{r}(A_i-P)\ge0.$$

令 $S_0=0$，$S_i=\sum_{j=1}^{i}(A_j-P)$，则条件等价于 $S_{l-1}\le S_r$。问题变为统计 $0\le i<j\le N$ 且 $S_i\le S_j$ 的有序下标对。

从左到右处理 $S_0,S_1,\ldots,S_N$。处理 $S_j$ 前，数据结构只保存下标小于 $j$ 的前缀和，查询其中不大于 $S_j$ 的数量并加入答案，然后再插入 $S_j$。这样既保留先后顺序，又保证不会把空区间算进去。

前缀和的绝对值可能很大，但最多只有 $N+1$ 个值。先排序去重并离散化，树状数组保存每种值出现的次数，前缀计数查询即可完成统计。相等的前缀和必须互相贡献答案，查询范围应包含当前位置。

正确性证明

非空区间 $[l,r]$ 与下标对 $(l-1,r)$ 一一对应，代数变形证明区间达标恰好等价于左前缀不大于右前缀。处理右端前缀 $S_r$ 时，树状数组恰好保存所有且仅有更早的前缀，因此查询准确统计以 $r$ 为右端点的达标区间。每个右端点处理一次，合计即为全部答案。

复杂度与其他满分做法

离散化排序与全部树状数组操作合计 $O(N\log N)$，空间 $O(N)$。也可以使用归并排序统计前缀序列中的非严格正序对，复杂度相同。

如果离散化后只用普通频次数组，每次逐个扫描所有不大于当前值的秩，时间仍可能达到 $O(N^2)$。前缀和取值很少时它会显得很快，但满范围并没有这种保证。即使改为扫描较短的一侧、用总数减去较大值频数，也只是改善常数；当大量前缀和互不相同且当前秩反复落在中间时，仍应按平方做法看待。

前缀和范围可达到 $\pm10^{15}$；答案最大为 $N(N+1)/2=500000500000$，两者都要用64位整数。树状数组单个累计次数不超过 $N+1$，用 int 即可。

常见错误与赛时路线

减去 $P$ 后元素可以为负数，因此不能套用非负数组的单调双指针：扩展区间可能让和增加，也可能减少。例如数组 $1,3,2$、$P=2$ 时答案为5，不能只取每个右端点的一段单调合法左端范围。

把非严格比较写成严格比较会漏掉平均值恰为 $P$ 的区间；例如只有一个数2、$P=2$，答案为1。漏掉 $S_0$ 会漏掉所有从第一天开始的区间。先把整个前缀和序列排序再直接计数，会破坏 $i<j$ 的先后条件。跨组未清空树状数组则会把上组前缀计入本组。

答案用32位整数的版本在 $N\le10000$ 时上界仅50005000，能正确获得30分；但不能把这一事实推广到满范围。赛时先实现整数比较的平方枚举保住30分，再从“区间和”为两前缀之差出发寻找满分算法。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, m, a[N], tr[N];
LL s[N], b[N];
void add(int x) {
	for (; x <= m; x += x & -x) tr[x] ++;
}
int query(int x) {
	int ans = 0;
	for (; x; x -= x & -x) ans += tr[x];
	return ans;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		int p;
		cin >> p;
		s[0] = b[0] = 0;
		for (int i = 1; i <= n; i ++) b[i] = s[i] = s[i - 1] + a[i] - p;
		sort(b, b + n + 1);
		m = unique(b, b + n + 1) - b;
		fill(tr, tr + m + 1, 0);
		LL ans = 0;
		for (int i = 0; i <= n; i ++) {
			int x = lower_bound(b, b + m, s[i]) - b + 1;
			ans += query(x);
			add(x);
		}
		cout << ans << "\n";
	}
	return 0;
}

T6 线路通票（pass）

简要题意

每组给出一个 $N\le10^5$ 个点、$M\le2\times10^5$ 条边的连通简单无向图，边权为不超过 $10^9$ 的正整数，以及 $S\ne T$、$U\ne V$。选择一条原图的 $S$ 到 $T$ 最短路，将它的边双向变为免费，输出能达到的最小 $U$ 到 $V$ 费用。每文件至多 $10$ 组，$\sum N\le2\times10^5$、$\sum M\le4\times10^5$。

一句话题解

四次最短路提取 $S$ 到 $T$ 的最短路有向无环图，沿它传播来自 $U$、$V$ 的最小接入费用，枚举另一个端点完成合并。

完整题解

1. 一段连续的免费行程就够了

暂时固定一条通票路线。它是一条简单路径：原边权均为正，原图最短路不可能包含绕圈。

若一条 $U$ 到 $V$ 的行程使用了通票，记它第一次进入通票路径的站为 $x$，最后一次离开的站为 $y$。中间的行程可以直接替换成沿通票路径从 $x$ 到 $y$ 免费移动，费用不会增加。即使原来多次离开又返回，也没有保留那些收费绕行的必要。

因此，只需考虑“付费到达 $x$，免费到达 $y$，付费到达 $V$”。设原图从 $U$、$V$ 到各站的最短距离分别为 $d_U,d_V$，其候选费用为

$$d_U[x]+d_V[y].$$

原图最短的接入路线即使碰巧使用了其他免费边，也只会让实际支付更少；而任意最优行程的首尾付费部分不会短于原图最短距离。因此对所有可共存的 $x,y$ 取最小值，能恰好得到使用通票的最优答案。还应与完全不用通票的 $d_U[V]$ 比较。

2. 关键限制：两个站必须能在同一张通票上

用 $d_S,d_T$ 表示从 $S$、$T$ 出发的原图最短距离，令 $D=d_S[T]$。一个站 $x$ 能出现在某条通票路径上，当且仅当

$$d_S[x]+d_T[x]=D.$$

但是，两个站分别满足这个条件，不代表它们能同时出现在同一条最短路上。例如菱形图有两条等长路线 $S\to a\to T$ 和 $S\to b\to T$，$a,b$ 分别在最短路上，却不能由同一张通票同时覆盖。若把两条路线全部免费，就会把本来需要付费的 $a$ 到 $b$ 行程错误地算成零。

3. 15 分：唯一最短路

若 $S$ 到 $T$ 的最短路唯一，通票没有选择余地。先求最短路并恢复这条路径，将它的边改为零，再求一次 $U$ 到 $V$ 的最短路即可，时间 $O((N+M)\log N)$。

即使没有唯一性保证，这个程序仍是在尝试一张合法通票，但可能不是最优通票，因此不能当成完整做法。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;
const int N = 1e5 + 10;
const LL inf = 4e18;
int n, m, S, T, U, V, id[N];
vector<PII> e[N];
LL ds[N], dt[N], du[N], dv[N], f[N], g[N];
void dijkstra(int s, LL d[]) {
	fill(d + 1, d + n + 1, inf);
	priority_queue<PLI, vector<PLI>, greater<PLI> > q;
	d[s] = 0, q.push({0, s});
	while (!q.empty()) {
		LL dist = q.top().first;
		int u = q.top().second;
		q.pop();
		if (dist != d[u]) continue;
		for (auto it : e[u]) {
			int v = it.first, w = it.second;
			if (d[v] > dist + w) d[v] = dist + w, q.push({d[v], v});
		}
	}
}
int par[N];
LL dist[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q --) {
		cin >> n >> m >> S >> T >> U >> V;
		for (int i = 1; i <= n; i ++) e[i].clear(), par[i] = 0;
		for (int i = 1; i <= m; i ++) {
			int a, b, c;
			cin >> a >> b >> c;
			e[a].push_back({b, c}), e[b].push_back({a, c});
		}
		dijkstra(S, ds);
		for (int u = T; u != S; ) {
			for (auto it : e[u]) if (ds[it.first] + it.second == ds[u]) {
				par[u] = it.first;
				break;
			}
			u = par[u];
		}
		fill(dist + 1, dist + n + 1, inf);
		priority_queue<PLI, vector<PLI>, greater<PLI> > q;
		dist[U] = 0, q.push({0, U});
		while (!q.empty()) {
			LL d = q.top().first;
			int u = q.top().second;
			q.pop();
			if (d != dist[u]) continue;
			for (auto it : e[u]) {
				int v = it.first, w = it.second;
				if (par[u] == v || par[v] == u) w = 0;
				if (dist[v] > d + w) dist[v] = d + w, q.push({dist[v], v});
			}
		}
		cout << dist[V] << "\n";
	}
	return 0;
}

4. 自然累计 30 分：把全部最短路边免费

当 $S=U$，从出发点就能免费到达所选通票上的任意站。只要确定最后在哪个站下车，再从那里付费走向 $V$ 即可。因此答案为所有满足 $d_S[x]+d_T[x]=D$ 的站中，$d_V[x]$ 的最小值。

可以统一前两档：把“出现在至少一条 $S$ 到 $T$ 最短路上的边”全部设为零后求最短路。当 $S=U$ 时，这相当于在所有可选下车站中取最优；当最短路唯一时，免费边集合恰好就是那一条路径。它在这两档都完整正确，累计 $30$ 分，但在一般输入中会错误混用互斥分支。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;
const int N = 1e5 + 10;
const LL inf = 4e18;
int n, m, S, T, U, V, id[N];
vector<PII> e[N];
LL ds[N], dt[N], du[N], dv[N], f[N], g[N];
void dijkstra(int s, LL d[]) {
	fill(d + 1, d + n + 1, inf);
	priority_queue<PLI, vector<PLI>, greater<PLI> > q;
	d[s] = 0, q.push({0, s});
	while (!q.empty()) {
		LL dist = q.top().first;
		int u = q.top().second;
		q.pop();
		if (dist != d[u]) continue;
		for (auto it : e[u]) {
			int v = it.first, w = it.second;
			if (d[v] > dist + w) d[v] = dist + w, q.push({d[v], v});
		}
	}
}
LL dist[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q --) {
		cin >> n >> m >> S >> T >> U >> V;
		for (int i = 1; i <= n; i ++) e[i].clear();
		for (int i = 1; i <= m; i ++) {
			int a, b, c;
			cin >> a >> b >> c;
			e[a].push_back({b, c}), e[b].push_back({a, c});
		}
		dijkstra(S, ds), dijkstra(T, dt);
		fill(dist + 1, dist + n + 1, inf);
		priority_queue<PLI, vector<PLI>, greater<PLI> > q;
		dist[U] = 0, q.push({0, U});
		while (!q.empty()) {
			LL d = q.top().first;
			int u = q.top().second;
			q.pop();
			if (d != dist[u]) continue;
			for (auto it : e[u]) {
				int v = it.first, w = it.second;
				if (ds[u] + w + dt[v] == ds[T] || ds[v] + w + dt[u] == ds[T]) w = 0;
				if (dist[v] > d + w) dist[v] = d + w, q.push({dist[v], v});
			}
		}
		cout << dist[V] << "\n";
	}
	return 0;
}

5. 25 分：小图求全源距离

当 $N\le300$，可以用 Floyd 求出任意两点间的最短距离 $d[x][y]$，时间 $O(N^3)$、空间 $O(N^2)$。

若将 $x$ 看作靠近 $S$ 的免费端点、$y$ 看作靠近 $T$ 的免费端点，则它们能共同出现在某条通票上，当且仅当

$$d_S[x]+d[x][y]+d_T[y]=D.$$

必要性来自最短路的子路径也是最短路。充分性来自拼接三段最短路：总长度恰为 $D$，若其中有重复顶点，则删去正长度的环会得到比 $D$ 更短的 $S$ 到 $T$ 路线，矛盾。

枚举满足等式的点对，同时考虑费用 $d_U[x]+d_V[y]$ 与 $d_U[y]+d_V[x]$。后者对应沿通票的反方向免费移动，不能漏掉。

下面的等价实现逐个起点运行 Dijkstra 获取所需距离，不存整张距离矩阵，时间 $O(N(N+M)\log N)$、空间 $O(N+M)$。它仍是小图全源最短路方法；容量按完整输入预留，超出小图档时会因真实计算量过大超时，而不是靠越界或主动退出区分分数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;
const int N = 1e5 + 10;
const LL inf = 4e18;
int n, m, S, T, U, V, id[N];
vector<PII> e[N];
LL ds[N], dt[N], du[N], dv[N], f[N], g[N];
void dijkstra(int s, LL d[]) {
	fill(d + 1, d + n + 1, inf);
	priority_queue<PLI, vector<PLI>, greater<PLI> > q;
	d[s] = 0, q.push({0, s});
	while (!q.empty()) {
		LL dist = q.top().first;
		int u = q.top().second;
		q.pop();
		if (dist != d[u]) continue;
		for (auto it : e[u]) {
			int v = it.first, w = it.second;
			if (d[v] > dist + w) d[v] = dist + w, q.push({d[v], v});
		}
	}
}
LL dist[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q --) {
		cin >> n >> m >> S >> T >> U >> V;
		for (int i = 1; i <= n; i ++) e[i].clear();
		for (int i = 1; i <= m; i ++) {
			int a, b, c;
			cin >> a >> b >> c;
			e[a].push_back({b, c}), e[b].push_back({a, c});
		}
		dijkstra(S, ds), dijkstra(T, dt), dijkstra(U, du), dijkstra(V, dv);
		LL ans = du[V];
		for (int i = 1; i <= n; i ++) {
			if (ds[i] + dt[i] != ds[T]) continue;
			dijkstra(i, dist);
			for (int j = 1; j <= n; j ++)
				if (ds[i] + dist[j] + dt[j] == ds[T])
					ans = min(ans, min(du[i] + dv[j], dv[i] + du[j]));
		}
		cout << ans << "\n";
	}
	return 0;
}

6. 55 分：组合已经掌握的性质

先判断 $S=U$，或者通过最短路 DAG 上的路径计数（只需将计数截到 $2$）判断最短路是否唯一。满足其中之一时用前述快速特例，否则用小图的全源最短路方案。这样能完整处理前三档，累计 $55$ 分。

这条路线可以做安全剪枝：若某个接入站的最低可能费用已经不小于当前答案，就跳过它；也可以把另一端的全局最小接入费用纳入下界。这些优化不会影响正确性，但最坏复杂度仍未改变。比如两条互斥的长最短路分别靠近 $U$、$V$，两端各自最便宜的站不能同时出现在通票上，下界就会持续偏小，仍需进行大量逐源最短路。不能把这种剪枝当成满分复杂度保证。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;
const int N = 1e5 + 10;
const LL inf = 4e18;
int n, m, S, T, U, V, id[N];
vector<PII> e[N];
LL ds[N], dt[N], du[N], dv[N], f[N], g[N];
void dijkstra(int s, LL d[]) {
	fill(d + 1, d + n + 1, inf);
	priority_queue<PLI, vector<PLI>, greater<PLI> > q;
	d[s] = 0, q.push({0, s});
	while (!q.empty()) {
		LL dist = q.top().first;
		int u = q.top().second;
		q.pop();
		if (dist != d[u]) continue;
		for (auto it : e[u]) {
			int v = it.first, w = it.second;
			if (d[v] > dist + w) d[v] = dist + w, q.push({d[v], v});
		}
	}
}
LL dist[N];
int ways[N];
bool cmp(int a, int b) { return ds[a] < ds[b]; }
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q --) {
		cin >> n >> m >> S >> T >> U >> V;
		for (int i = 1; i <= n; i ++) e[i].clear();
		for (int i = 1; i <= m; i ++) {
			int a, b, c;
			cin >> a >> b >> c;
			e[a].push_back({b, c}), e[b].push_back({a, c});
		}
		dijkstra(S, ds), dijkstra(T, dt), dijkstra(U, du), dijkstra(V, dv);
		LL ans = du[V];
		for (int i = 1; i <= n; i ++) id[i] = i, ways[i] = 0;
		sort(id + 1, id + n + 1, cmp);
		ways[S] = 1;
		for (int i = 1; i <= n; i ++) {
			int u = id[i];
			for (auto it : e[u])
				if (ds[u] + it.second == ds[it.first])
					ways[it.first] = min(2, ways[it.first] + ways[u]);
		}
		if (S == U || ways[T] == 1) {
			LL x = inf, y = inf;
			for (int i = 1; i <= n; i ++) if (ds[i] + dt[i] == ds[T])
				x = min(x, du[i]), y = min(y, dv[i]);
			ans = min(ans, x + y);
		} else for (int i = 1; i <= n; i ++) {
			if (ds[i] + dt[i] != ds[T]) continue;
			dijkstra(i, dist);
			for (int j = 1; j <= n; j ++)
				if (ds[i] + dist[j] + dt[j] == ds[T])
					ans = min(ans, min(du[i] + dv[j], dv[i] + du[j]));
		}
		cout << ans << "\n";
	}
	return 0;
}

7. 满分：在最短路 DAG 上合并状态

只保留可能出现在通票上的边，并按 $d_S$ 增大的方向定向。原图边 $(u,v,w)$ 形成有向边 $u\to v$，需满足

$$d_S[u]+w=d_S[v],\qquad d_S[v]+d_T[v]=D.$$

由于 $w>0$，沿每条有向边 $d_S$ 严格增加，因此这个图是 DAG。按 $d_S$ 递增处理所有点就是一个拓扑序。

定义 $f[v]$ 为所有能够在这个 DAG 上到达 $v$ 的站 $x$ 中，$d_U[x]$ 的最小值；允许 $x=v$。初始化 $f[v]=d_U[v]$，每条有向边 $u\to v$ 执行 $f[v]=\min(f[v],f[u])$。

于是 $f[v]+d_V[v]$ 就覆盖了“从 $U$ 接入某个前驱站，沿通票正方向到 $v$ 后离开”的全部选择。为了覆盖反向免费行程，再对称维护 $g[v]$，它传播 $d_V$ 的最小值，使用候选 $g[v]+d_U[v]$。

这两个最小值各自来自一个真实前驱，不要求它们来自同一条路径：每次计算答案只使用其中一个最小值和当前站，DAG 可达性已经保证这两个端点能够共存。千万不能把两个彼此独立的最小值直接相加。

最终答案是 $d_U[V]$ 与所有有效站的上述两类候选的最小值。

8. 复杂度与实现

四次 Dijkstra、一次排序和一次 DAG 扫描，总时间 $O((N+M)\log N)$，空间 $O(N+M)$。普通最短距离可能达到约 $10^{14}$，应使用 long long；加法也必须保持 64 位。算法不使用递归，因此长链不会造成递归栈溢出。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;
const int N = 1e5 + 10;
const LL inf = 4e18;
int n, m, S, T, U, V, id[N];
vector<PII> e[N];
LL ds[N], dt[N], du[N], dv[N], f[N], g[N];
void dijkstra(int s, LL d[]) {
	fill(d + 1, d + n + 1, inf);
	priority_queue<PLI, vector<PLI>, greater<PLI> > q;
	d[s] = 0, q.push({0, s});
	while (!q.empty()) {
		LL dist = q.top().first;
		int u = q.top().second;
		q.pop();
		if (dist != d[u]) continue;
		for (auto it : e[u]) {
			int v = it.first, w = it.second;
			if (d[v] > dist + w) d[v] = dist + w, q.push({d[v], v});
		}
	}
}
bool cmp(int a, int b) { return ds[a] < ds[b]; }
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q --) {
		cin >> n >> m >> S >> T >> U >> V;
		for (int i = 1; i <= n; i ++) e[i].clear(), id[i] = i;
		for (int i = 1; i <= m; i ++) {
			int a, b, c;
			cin >> a >> b >> c;
			e[a].push_back({b, c}), e[b].push_back({a, c});
		}
		dijkstra(S, ds), dijkstra(T, dt), dijkstra(U, du), dijkstra(V, dv);
		sort(id + 1, id + n + 1, cmp);
		LL ans = du[V];
		for (int i = 1; i <= n; i ++) f[i] = du[i], g[i] = dv[i];
		for (int i = 1; i <= n; i ++) {
			int u = id[i];
			if (ds[u] + dt[u] != ds[T]) continue;
			ans = min(ans, min(f[u] + dv[u], g[u] + du[u]));
			for (auto it : e[u]) {
				int v = it.first, w = it.second;
				if (ds[u] + w == ds[v] && ds[v] + dt[v] == ds[T]) {
					f[v] = min(f[v], f[u]);
					g[v] = min(g[v], g[u]);
				}
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

9. 赛时辨别与错误方向

• 看到 $N\le300$，先写出点对条件并用全源最短路获得小图分。
• 看到“只选一条最短路”，不能将最短路图中所有边直接免费。菱形的两个不同分支就是最小的结构提醒。
• 同一张通票的边可以双向使用。例如一条链上 $U=T,V=S$，答案为零；只在 $S$ 到 $T$ 的正方向做一次 DP 会漏解。
• 任取一条最短路不够；按正反邻接顺序各取一条再择优，也会漏掉第三条或更复杂的最优路线。
• 先固定最靠近 $U$ 的通票站，再挑选可共存的出口也不正确，即使对 $V$ 对称处理后取较优值仍可能漏解。例如有三条等长的三段路线，每段原价均为 $100$；$U$ 到第一条、中间一条路线的首个内部站分别另连费用 $1,2$ 的边，$V$ 到第三条、中间一条路线的最后一个内部站分别另连费用 $1,2$ 的边。两端各自最近的选择被第一、第三条路线吸引，而中间路线的正确费用只有 $2+2=4$；最近端点贪心得到 $102$。需要同时权衡接入与离开两端，而不是先锁死其中一端。
• 可以完全不用通票，答案初始化应保留原图的 $U$ 到 $V$ 最短距离。
• 不要在最后把正确的 64 位答案放进 int，否则例如 $4\times10^9$ 的费用会溢出。