P2993 [FJOI2014]最短路径树问题

    • 203通过
    • 551提交
  • 题目提供者 JerryXie
  • 评测方式 云端评测
  • 标签 各省省选 2014 福建
  • 难度 省选/NOI-
  • 时空限制 3000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给一个包含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行,每行三个正整数Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000),表示Ai和Bi间有一条长度为Ci的边。

    数据保证输入的是连通的无向图。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    6 6 4
    1 2 1
    2 3 1
    3 4 1
    2 5 1
    3 6 1
    5 6 1
    输出样例#1: 复制
    3 4

    说明

    对于所有数据n<=30000,m<=60000,2<=K<=n。

    数据保证最短路径树上至少存在一条长度为K的路径。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。