問題
背景
鳗鱼王国的王子由于缺乏运动,被国王和下属们指出。因此,鳗鱼王国的王子想在城堡附近散步,并正在考虑散步的路线。鳗鱼王国的王子非常讨厌运动,因此希望路线尽可能短。然而,由于鳗鱼王子的身体非常长,如果路线太短,尾巴可能在头部返回城堡之前就已经到达城堡,这样可能无法被认作是从城堡出发出去的。因此,他想知道适度短的散步路线。
課題
你的工作是,当给定图时, 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 ,则输出 。请注意,图的边是有向的。