羽化而登仙(Feather Ascension)

2026 年青岛市中小学程序设计竞赛高中组 T2

你有一张 $n$ 个点， $m$ 条边的无向图。第 $i$ 条边有边权 $2^i$ 。

现在，有 $q$ 组询问。每次询问包含两个点 $x,y$ ，请计算两点间的最短路径，答案对 $998,244,353$ 取模。如果这样的路径不存在，你需要输出 −1。

注意，题目要求对答案取模，而不是取模以后的值最小。

第一行三个整数 $n,m,q$ ，分别表示图的点数、图的边数和询问次数。

接下来 $m$ 行，每行两个整数 $u_i,v_i$ ，表示一条连接 $u,v$ 的边，其边权为 $2^i$ 。

接下来 $q$ 行，每行两个整数 $x_i,y_i$ ，表示一次询问。

$q$ 行，每行一个整数，表示询问的答案。

测试点编号	$n$	$m$	$q$	特殊性质
1 ~ 3	$\le 10$			无
4 ~ 6	$\le 10^5$	$= n - 1$	$\le 10^5$	A
7 ~ 9	$\le 10^5$	$= n$	$\le 10^5$	A
10 ~ 13	$\le 2000$			无
14 ~ 17	$\le 10^5$	$\le \min\{10^5, n + 100\}$	$\le 10^5$	A
18 ~ 21	$\le 10^5$	$\le 10^5$	$\le 10^5$	无
22 ~ 25	$\le 3 \times 10^5$			无

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	25	2~8	小规模与边界测试数据
2	30	9~16	中等规模测试数据
3	35	17~25	满规模极限测试数据

出处：原题链接

#R1148. 羽化而登仙(Feather Ascension)