← 返回题目列表

Codeforces · 1366/F

F. 在图表中慢跑

中文机器翻译题面 查看原题

给你一个简单的加权连通无向图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。

图中长度 $$$k$$$ 的路径是 $$$k+1$$$ 顶点 $$$v_1, v_2, \dots, v_{k+1}$$$ 的序列,使得对于每个 $$$i$$$ $$$(1 \le i \le k)$$$,边 $$$(v_i, v_{i+1})$$$ 存在于图表。从某个顶点 $$$v$$$ 开始的路径也有顶点 $$$v_1=v$$$。请注意,边和顶点允许多次包含在路径中。

路径的权重是其中边的总权重。

对于从 $$$1$$$ 到 $$$q$$$ 的每个 $$$i$$$,考虑一条从顶点 $$$1$$$ 开始、长度为最大权重 $$$i$$$ 的路径。这些 $$$q$$$ 路径的权重总和是多少?

答案可能相当大,因此打印它对 $$$10^9+7$$$ 取模。

输入

第一行包含三个整数 $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n \le 2000$$$; $$$n - 1 \le m \le 2000$$$; $$$m \le q \le 10^9$$$) — 图中的顶点数,边数图中的长度以及答案中应包含的长度数。

接下来的 $$$m$$$ 行包含一条边的描述:三个整数 $$$v$$$、$$$u$$$、$$$w$$$ ($$$1 \le v, u \le n$$$; $$$1 \le w \le 10^6$$$) - 两个顶点 $$$v$$$ 和 $$$u$$$ 通过权重为 $$$w$$$ 的无向边。该图不包含循环,也不包含多重边。保证给定的边形成连通图。

输出

打印单个整数 - 从顶点 $$$1$$$ 开始的路径权重总和,长度为 $$$1, 2, \dots, q$$$ 模 $$$10^9+7$$$。

示例

输入 #1

7 8 25
1 2 1
2 3 10
3 4 2
1 5 2
5 6 7
6 4 15
5 3 1
1 7 3

输出 #1

4361

输入 #2

2 1 5
1 2 4

输出 #2

60

输入 #3

15 15 23
13 10 12
11 14 12
2 15 5
4 10 8
10 2 4
10 7 5
3 10 1
5 6 11
1 13 8
9 15 4
4 2 9
11 15 1
11 12 14
10 8 12
3 6 11

输出 #3

3250

输入#4

5 10 10000000
2 4 798
1 5 824
5 2 558
4 1 288
3 4 1890
3 1 134
2 3 1485
4 5 284
3 5 1025
1 2 649

输出#4

768500592

注意

这是第一个示例的图表:

一些最大权重路径是:

- 长度 $$$1$$$:边 $$$(1, 7)$$$ — 重量 $$$3$$$;
- 长度 $$$2$$$:边 $$$(1, 2), (2, 3)$$$ — 重量 $$$1+10=11$$$;
- 长度 $$$3$$$:边 $$$(1, 5), (5, 6), (6, 4)$$$ — 重量 $$$2+7+15=24$$$;
- 长度 $$$4$$$:边 $$$(1, 5), (5, 6), (6, 4), (6, 4)$$$ — 重量 $$$2+7+15+15=39$$$;
- $$$\点$$$

所以答案是 $$$25$$$ 项的总和:$$$3+11+24+39+\dots$$$

在第二个示例中,最大权重路径的权重为 $$$4$$$、$$$8$$$、$$$12$$$、$$$16$$$ 和 $$$20$$$。