题解

思路

先用 Kruskal 的结构把“选择最小生成树”改写成“寻找一条缩点后不重复轻边块的最短路径”，再用状态压缩最短路枚举。满分优化的关键是：大小不超过三的轻边块一旦被重复访问，就能用至多两条轻边严格缩短，因而只需记录大块。

做法

最小生成树的结构

只看权值为 $a$ 的边，并把它们的连通块记为“轻边块”。Kruskal 算法说明，每棵最小生成树都满足：

1. 在每个轻边块内部选一棵只含 $a$ 边的生成树；
2. 缩点后，用若干条 $b$ 边把所有轻边块连成树。

因此，一条从 $1$ 到 $p$ 的路径能包含在某棵最小生成树中，当且仅当它在缩点后不重复经过同一个轻边块。块内使用的简单 $a$ 边路径可以补成块内生成树，缩点后的简单路径也可以补成块间生成树。

子任务 1：枚举生成树

枚举恰好 $n-1$ 条边的子集，判断它是否为生成树且总权值等于最小生成树权值。对每棵合法树从 $1$ 遍历，逐点取距离最小值。

复杂度为 $O\!\left(\binom m{n-1}(n+m)\right)$，适用于 $n\le9,m\le15$。

子任务 2：记录所有轻边块

设轻边块数为 $K$。在状态图上运行 Dijkstra：状态 $(v,S)$ 表示当前位于点 $v$，并且已经访问过的轻边块集合为 $S$。

• 走 $a$ 边时仍在同一块，集合不变；
• 走连接不同轻边块的 $b$ 边时，目标块不能已经在 $S$ 中，随后把它加入 $S$；
• 两端位于同一轻边块的 $b$ 边不可能出现在最小生成树中，直接忽略。

这恰好枚举了缩点后不重复块的路径。复杂度为 $O(2^K(n+m)\log(2^Kn))$，空间复杂度为 $O(2^Kn)$。

子任务 3：只记录大块

若一个轻边块至多有三个点，则任意两点间存在一条至多含两条 $a$ 边的简单路径。若某条候选最短路离开该块后又回到该块，可以把两次出现之间的部分替换为块内路径。被替换部分至少含两条 $b$ 边，代价至少为 $2b$；替换后的代价至多为 $2a<2b$。所以最短路一定不会重复经过这种小块，无须在状态中记录它。

只给大小至少为 $4$ 的轻边块分配二进制位。这样的块至多有 $\lfloor70/4\rfloor=17$ 个。继续使用上一子任务的 Dijkstra；小块允许在状态图中重复，但上述严格变短论证保证最短答案不会利用这种重复。

设大块数为 $L\le17$，满分复杂度为 $O(2^L(n+m)\log(2^Ln))$，空间复杂度为 $O(2^Ln)$。

复杂度

枚举层复杂度为 $O\!\left(\binom m{n-1}(n+m)\right)$。全块掩码层复杂度为 $O(2^K(n+m)\log(2^Kn))$。满分层令大块数为 $L\le17$，复杂度为 $O(2^L(n+m)\log(2^Ln))$，空间复杂度为 $O(2^Ln)$。

正确性说明

Kruskal 结构刻画了全部最小生成树。状态图中的每条受限路径都不重复大块；若它重复小块，使用块内至多两条轻边的路径可严格缩短，所以最短状态路径不重复任何块。于是状态图最短路可补成一棵最小生成树。反过来，任意最小生成树中的 $1$ 到 $p$ 路径缩点后都是简单路径，必然被状态图枚举。因此算法输出恰为题目要求的最小值。