QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB Total points: 100
[+4]

# 7775. 【模板】矩阵快速幂

Statistics

给定一张 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 分):n3106k1018
  • Subtask #2(15 分):m=2n2,且对任意 1i<n,存在权值相等的 (i,i+1)(i+1,i)
  • Subtask #3(20 分):m2n2,且对任意 (u,v),存在权值相等的 (v,u),注意 u 可以等于 v。依赖于 Subtask #2。
  • Subtask #4(15 分):n3106,依赖于 Subtask #1。
  • Subtask #5(15 分):k1018,依赖于 Subtask #1。
  • Subtask #6(25 分):无特殊性质。依赖于 Subtask #3,#4,#5。

对于所有数据,1S61T1042n3001m2n1k10641u,vn1w1018。保证 n2×105n32.7×107

时间限制 3.00s,空间限制 2G。