[集训队互测 2023] 矩阵快速幂

Luogu

IDLGP10000

Time3000ms

Memory2048MB

DifficultyP7

集训队互测2023O2优化

给定一张 $n$ 个点 $m$ 条边的边带权有向图，可能有重边和自环。求从 $1$ 出发到每个点恰好走 $k$ 条边的路径权值的最小值 **对 $998244353$ 取模后的结果**。若路径不存在则输出 $-1$。多组数据。路径权值的定义是路径上所有边的权值之和。 ## Input 第一行一个整数 $S$ 表示子任务编号。第二行一个整数 $T$ 表示数据组数。对于每组数据： - 第一行三个整数 $n, m, k$。 - 接下来 $m$ 行，每行三个整数 $u, v, w$ 表示一条有向边。 ## Output 对于每组数据，输出一行 $n$ 个由空格隔开的整数表示答案。 [samples] ## Background 请注意：**本题不是矩阵快速幂模板题**。 ## Note - Subtask #1（$10$ 分）：$\sum n ^ 3\leq 10 ^ 6$，$k\leq 10 ^ {18}$。 - Subtask #2（$15$ 分）：$m = 2n - 2$，且对任意 $1\leq i < n$，存在权值相等的 $(i, i + 1)$ 和 $(i + 1, i)$。 - Subtask #3（$20$ 分）：$m\geq 2n - 2$，且对任意 $(u, v)$，存在权值相等的 $(v, u)$，注意 $u$ 可以等于 $v$。依赖于 Subtask #2。 - Subtask #4（$15$ 分）：$\sum n ^ 3\leq 10 ^ 6$，依赖于 Subtask #1。 - Subtask #5（$15$ 分）：$k\leq 10 ^ {18}$，依赖于 Subtask #1。 - Subtask #6（$25$ 分）：无特殊性质。依赖于 Subtask #3，#4，#5。对于所有数据，$1\leq S\leq 6$，$1\leq T\leq 10 ^ 4$，$2\leq n\leq 300$，$1\leq m\leq 2n$，$1\leq k\leq 10 ^ {64}$，$1\leq u, v\leq n$，$1\leq w\leq 10 ^ {18}$。保证 $\sum n \leq 2\times 10 ^ 5$ 且 $\sum n ^ 3 \leq 2.7 \times 10 ^ 7$。题解在附件 `paper.pdf` 中。

Samples

Input #1

1
1
5 5 101
1 2 1
2 3 100
3 4 10000
4 2 1000000
2 5 10

Output #1

-1 -1 33333401 -1 33333311

Input #2

见下发文件 ex_matrix1.in

Output #2

见下发文件 ex_matrix1.ans

Input #3

见下发文件 ex_matrix2.in

Output #3

见下发文件 ex_matrix2.ans

API Response (JSON)

{
  "problem": {
    "name": "[集训队互测 2023] 矩阵快速幂",
    "description": {
      "content": "给定一张 $n$ 个点 $m$ 条边的边带权有向图，可能有重边和自环。求从 $1$ 出发到每个点恰好走 $k$ 条边的路径权值的最小值 **对 $998244353$ 取模后的结果**。若路径不存在则输出 $-1$。多组数据。 路径权值的定义是路径上所有边的权值之和。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 2097152
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10000"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张 $n$ 个点 $m$ 条边的边带权有向图，可能有重边和自环。求从 $1$ 出发到每个点恰好走 $k$ 条边的路径权值的最小值 **对 $998244353$ 取模后的结果**。若路径不存在则输出 $-1$。多组数据。\n\n路径权值的定义是路径上所有边的权值之和。\n\n## Input\n\n第一行一个整数 $S$ 表示子任务编号。\n\n第二行一个整数 $T$ 表示数据组数。\n\n对于每组数据：\n\n-...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments