← 返回题目

题库练习「FJOI2014」最短路径树问题

← 上一题下一题 →

A6816 | $「FJOI2014」最短路径树问题$

来源省选

时间限制5s

内存限制512MB

通过 / 提交0/0

题目描述

给一个包含 $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$ 个点的路径最长为多长，第二个整数表示这样的不同的最长路径有多少条。

输入输出样例

输入 #1

输出 #1

3 4

C++ 编辑器

输入

输出