← 返回题目列表

AtCoder · utpc2013_10

J. 第K次循环

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

問題

背景

鳗鱼王国的王子由于缺乏运动,被国王和下属们指出。因此,鳗鱼王国的王子想在城堡附近散步,并正在考虑散步的路线。鳗鱼王国的王子非常讨厌运动,因此希望路线尽可能短。然而,由于鳗鱼王子的身体非常长,如果路线太短,尾巴可能在头部返回城堡之前就已经到达城堡,这样可能无法被认作是从城堡出发出去的。因此,他想知道适度短的散步路线。

課題

你的工作是,当给定图时, 0 以顶点出发并返回到顶点的 0 路径中, 1, 2, ..., K 求出第几短路径的长度的程序。

图不一定是简单图(即可能存在自环或多重边)。路径中可以多次经过同一个顶点。特别地,除开始和结束外的顶点 0 。路径是通过经过的边的序列来区分的。也就是说,即使经过的顶点序列相同,如果经过的边不同,也视为不同的路径。路径的长度定义为经过的边的权重的总和。在本问题中,只考虑至少经过1条边的路径(即长度为 0 的路径不予考虑)。对于长度相同的2条路径,可以随意赋予不同的顺序。也就是说,顶点 0 以顶点出发并返回到顶点的 0 返回的所有路径按长度升序排列时,输出开头 K 条路径的长度。

但是,由于军事机密的原因,鳗鱼王国的地图不会公开。因此,在今天的比赛中,将使用如下方式生成的随机图来进行程序的正确性判断。图的 M 条边是独立生成的。对于每条边,其起点和终点分别 N 从顶点中均匀选择。每条边的权重也从 1 减去 1,000,000,000 的整数中均匀选择。实际上,输入是使用该程序生成的。用于初始化伪随机数生成器的程序的第四个参数值使用了 1 以上 1,000,000 以下的任意整数。

配点

200

入力

输入按以下格式给出。

N M K
U1 V1 C1
U2 V2 C2
...
UM VM CM

第一行的 N,M 表示图的顶点数和边数。K 表示所要寻找的路径数。接下来的 M 行表示图的边。每个 i 行表示顶点间的权重 Ui,Vi 输入是按照指定方法生成的(详情如上所示) Ci 的边缘。

制約

输入中的每个变量都满足以下约束。

  • N = 25,000
  • M = 105
  • K = 105
  • 输出第
  • 0 \leq Ui,Vi \lt N

出力

输出是 由 K 行组成。i (1 \leq i \leq K) 在线 i 短路径的长度。但如果不存在这样的路径,则输出 -1 。

入力例1

3 3 5
0 1 1
1 2 1
2 0 1

输入示例 1 的输出示例 路径

3
6
9
12
15

本输入。 N,M,K 请注意,没有遵守关于图和图的生成方法的约束。以下的输入示例也同样适用。

入力例2

2 4 5
0 0 2
0 0 3
0 1 1000
0 1 10000

输入示例 2 的输出示例

2
3
4
5
5

图不一定是简单图,可能存在自环或多重边。

入力例3

3 3 3
0 1 1
0 2 1
1 2 1

输入示例 3 的输出示例

-1
-1
-1

如果路径的数量 i 少于i 在线 -1 ,则输出 。请注意,图的边是有向的。