题解

思路

在已经乘坐 $t$ 次航班时，只有 $d_i\le t$ 的边可用。随 $t$ 增大，图只会在某些门槛 $d_i$ 处加边。在两个相邻门槛之间，每一步使用同一张图转移，因此可用布尔邻接矩阵的快速幂跨过大段时间。

做法

子任务 1：航班序列搜索

限制搜索深度为 $\max d_i+n$，从城市 $1$ 开始枚举每次可乘坐的航线。所有边激活后，若某个当前城市能到终点，去掉环后最短路不超过 $n-1$，因此该深度上界充分。

子任务 2：逐时刻可达集合 DP

设 $R_t$ 为恰好乘坐 $t$ 次航班后可能所在的城市集合。枚举全部航线，对每条满足 $d_i\le t$ 且 $a_i\in R_t$ 的边，将 $b_i$ 放入 $R_{t+1}$。扫描到 $\max d_i+n$ 即可。

子任务 3：事件扫描与布尔矩阵快速幂

按 $d_i$ 排序航线。在时刻 $t$ 维护恰好走 $t$ 步的可达集合 $R$与当前激活图 $G$。若下一门槛为 $T$：

1. 先从 $R$ 作多源 BFS，若到城市 $n$ 的最短距离不超过 $T-t$，立即得到最小答案；
2. 否则用布尔矩阵 $A_G^{T-t}$ 将 $R$ 精确推进到时刻 $T$；
3. 加入所有 $d_i=T$ 的航线。

全部航线加入后再做一次多源 BFS。若仍不可达则输出 Impossible。

布尔矩阵的乘法使用位集合实现：若 $A_{ik}=1$，就将 $B$ 的第 $k$ 行并入结果第 $i$ 行。

复杂度

第一层为指数级航班序列枚举；第二层时间复杂度为 $O((\max d_i+n)m)$，空间 $O(n)$；满分做法最多处理 $m$ 个门槛，复杂度为 $O(mn^3\log D/w)$ 位运算，空间 $O(n^2)$，其中 $D=10^9$、$w$ 为机器字长。

正确性证明

在相邻门槛之间图不变，布尔邻接矩阵的 $k$ 次幂恰好表示长度为 $k$ 的有向游走可达性，所以快速幂得到的集合正好是门槛时刻的全部可能城市。每个区间内，任何最早到达都是从当前可达集合出发的最短路，因此 BFS 能精确检出是否在下一门槛前到达。若未到达，按时间顺序加入门槛边并继续，不会遗漏任何合法方案。