给定一张 n 个点 m 条边的边带权有向图,可能有重边和自环。求从 1 出发到每个点恰好走 k 条边的路径权值的最小值 对 998244353 取模后的结果。若路径不存在则输出 −1。多组数据。
路径权值的定义是路径上所有边的权值之和。
输入格式
第一行一个整数 S 表示子任务编号。
第二行一个整数 T 表示数据组数。
对于每组数据:
- 第一行三个整数 n,m,k。
- 接下来 m 行,每行三个整数 u,v,w 表示一条有向边。
输出格式
对于每组数据,输出一行 n 个由空格隔开的整数表示答案。
样例 1
输入
1 1 5 5 101 1 2 1 2 3 100 3 4 10000 4 2 1000000 2 5 10
输出
-1 -1 33333401 -1 33333311
样例 2
见下发文件 ex_matrix1.in/ans
。
样例 3
见下发文件 ex_matrix2.in/ans
。
数据范围
- Subtask #1(10 分):∑n3≤106,k≤1018。
- Subtask #2(15 分):m=2n−2,且对任意 1≤i<n,存在权值相等的 (i,i+1) 和 (i+1,i)。
- Subtask #3(20 分):m≥2n−2,且对任意 (u,v),存在权值相等的 (v,u),注意 u 可以等于 v。依赖于 Subtask #2。
- Subtask #4(15 分):∑n3≤106,依赖于 Subtask #1。
- Subtask #5(15 分):k≤1018,依赖于 Subtask #1。
- Subtask #6(25 分):无特殊性质。依赖于 Subtask #3,#4,#5。
对于所有数据,1≤S≤6,1≤T≤104,2≤n≤300,1≤m≤2n,1≤k≤1064,1≤u,v≤n,1≤w≤1018。保证 ∑n≤2×105 且 ∑n3≤2.7×107。
时间限制 3.00s,空间限制 2G。