曾经是茂密森林的土地被人类破坏了,生活在那里的动物也消失了。这是稍后的故事。
一直为所欲为的人类终于注意到了地球的尖叫声。人类对过去的行为感到遗憾,并开始开展保护环境和再生失去的森林的活动。
绿树正慢慢回到狐狸二郎和他的朋友们居住的地方。二郎和他的动物朋友们回到了他们熟悉的地方,想要再次玩耍。
新再生的森林里还有一个动物游乐场。动物们想要重建连接操场的道路,以便它们可以在操场之间来回走动,但由于它们还不习惯新的森林,所以他们决定让道路尽可能简单。
具体来说,我们希望从任何游乐场到任何其他游乐场都只有一条路径。这样,您就可以到达游乐场,而不必担心在新森林中迷路。创建这样一条路径的方法可能有很多种,所以让我们选择一种能够最小化路径总长度的方法。
你能帮助动物们在新森林里舒适地生活吗?
課題
首先,我们向仅由一个顶点组成的图添加顶点和边,最后增加顶点数量。 使其成为 N 。从一开始就存在的顶点有数字 0 已附加,并且顶点 在 i 之后立即添加的顶点有一个编号 i+1 可以添加 。
执行以下程序:
- 具有以下参数的过程 构造(N、M、E):
- N -- 顶点数。每个顶点按照添加顺序添加。0到N-1 它们的编号最大为。
- M -- 可用边数。
- E -- 表示有关可用边缘的信息的二维数组。 0 ≤ i < M 对于 ,边缘 i 是顶点 E[i][0] 和 E[i][1] 其长度为E[i][2]。0 ≤ E[i][0] < E[i][1] < N, 1 ≤ E[i][2] ≤ 1 000 000 000 可以假设。
例

図 1
如图1所示 N = 5, M = 8,
| E = 考虑 | 0 | 1 | 8 | ||
| 0 | 2 | 7 | |||
| 0 | 3 | 1 | |||
| 1 | 2 | 3 | |||
| 1 | 4 | 7 | |||
| 2 | 3 | 2 | |||
| 2 | 4 | 6 | |||
| 3 | 4 | 9 |
的情况。在这种情况下,构造满足答案输出为4次。以下是正确的 显示如何调用答案:
| 次数 (x) | 致电 |
|---|---|
| 1 | 答案(8) |
| 2 | 答案(10) |
| 3 | 答案(6) |
| 4 | 答案(12) |
小課題
下面,在一次执行中 构造 调用参数 P 之和,即最终图的边数为 M 。
小課題 1 (16 点)
- 1 ≤ N ≤ 1 000
- 0 ≤ M ≤ 2 000
小課題 2 (24 点)
- 1 ≤ N ≤ 5 000
- 0 ≤ M ≤ 60 000
小課題 3 (59 点)
- 1 ≤ N ≤ 20 000
- 0 ≤ M ≤ 60 000
小課題 4 (1 点)
- 1 ≤ N ≤ 100 000
- 0 ≤ M ≤ 200 000
实施细节
制限
- CPU时间限制:1.5秒
- 内存限制:256 MB
注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。
接口 (API)
- 实现文件夹:animals2/(原型: 动物2.zip)
- 参赛者实现的文件:animals2.cpp
- 提交文件接口:animals2.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。- 1 行目: N, M 用空格分隔。
- 第2行到M+1: 对于 0 ≤ i < M 对于 ,i+2 行包含三个整数 E[i][0], E[i][1], E[i][2] 用空格分隔。
- 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
注意:示例评分程序按以下格式写入输出。- 从第 1 行开始 N-1 它们的编号最大为 行目: 0 ≤ i < N-1 ,i+1 可以添加 行是 代表 构造是i 时间 包含调用 答案 时的返回值。