#PQJ1422x7775. QOJ 1422_7775

    ID: 2604 传统题 3000ms 2048MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测快速幂最短路

QOJ 1422_7775

标题: 【模板】矩阵快速幂 - Problem - QOJ.ac

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

Statistics

The problem was used in the following contests:

给定一张 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。