#2259. 「FJOI2014」最短路径树问题

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给一个包含 n 个点, m 条边的无向连通图。从顶点 1 出发,往其余所有点分别走一次并返回。

往某一个点走时,选择总长度最短的路径走。若有多条长度最短的路径,则选择经过的顶点序列字典序最小的那条路径(如路径 A 1,32,11 ,路径 B 1,3,2,11 ,路径 B 字典序较小。注意是序列的字典序的最小,而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回,然后往其他点走,直到所有点都走过。

可以知道,经过的边会构成一棵最短路径树。请问,在这棵最短路径树上,最长的包含 k 个点的简单路径长度为多长?长度为该最长长度的不同路径有多少条?

这里的简单路径是指:对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同,点 A 到点 B 的路径和点 B 到点 A 视为同一条路径。

输入格式

第一行输入三个正整数 n,m,k ,表示有 n 个点 m 条边,要求的路径需要经过 k 个点。
接下来输入 m 行,每行三个正整数 A_i,B_i,C_i 1\leq A_i,B_i\leq n,1\leq C_i\leq 10000 ),表示 A_i B_i 间有一条长度为 C_i 的边。数据保证输入的是连通的无向图。

输出格式

输出一行两个整数,以一个空格隔开,第一个整数表示包含 k 个点的路径最长为多长,第二个整数表示这样的不同的最长路径有多少条。

样例

样例输入

6 6 4
1 2 1
2 3 1
3 4 1
2 5 1
3 6 1
5 6 1

样例输出

3 4

数据范围与提示

对于所有数据, n\leq 30000,m\leq 60000 2\leq k\leq n
数据保证最短路径树上至少存在一条长度为 k 的路径。