/ MYOJ / 题库 /

藩镇地铁

藩镇地铁

题目背景

某一天,fz20181223又在专心致志地建设祂的地铁,可某一天勘测地形时,祂发现邻村的绿绵羊蒟蒻因为没有软妹币只能造公交……于是,为了发扬人道主义精神对绵羊村进行铁路援助,fz20181223计划修一条高铁从藩镇到绵羊村。

题面描述

我们可以把fz20181223的地铁路线图和绿绵羊的公交路线图看作一个 nn 个点 mm 条边的图。这张图可以分成两个部分,这两个部分都是连通图,但互相不连通。给出这个图里每一条边的起点 xx ,终点 yy 和经过这一条边所需要的时间 ww 。现在,你需要在这两个图之间新建一条边,长度为 ff ,求连通后 需要最长时间的路线需要的最短时间 是多少。

输入输出格式

输入格式

11 行:两个数,代表 nnmm
22 ~ m+1m+1 行:每行3个数,分别代表 xxyyww
m+2m+2 行:1个数,为 ff

输出格式

一行,一个数,代表高铁通车后需要最长时间的路线需要的最短时间是多少。

输入输出样例

输入样例#1
7 6
1 2 2
2 4 8
1 4 1
2 5 5
3 6 3
6 7 4
10
输出样例#1
19

说明


如图,连接 2266 ,在这种情况下需要最长时间的路线为7->6->2->5,需要时间为 1919 。其他连接方法得出的结果均大于 1919


对于 3030 %的数据, 11nn10010011mm10001000
对于 6060 %的数据, 11nn30030011mm20002000
对于另外 1010 %的数据,保证图两部分的形态都是菊花状,如这样:

对于 100100 %的数据, 11xx , yynn50050011mm6000600011ww , ff10001000
数据保证两个不连通部分点数的比值在 13\frac{1}{3}33 之间,简单来说,就是两个不连通部分中点数多的部分的点数不超过点数少的部分的点数的 33 倍。
另外,绿绵羊就是出题人limingyang的代号(不会把不会吧还有人不知道这个?)
而fz20181223正是本场比赛的凉心验题人之一哦~
fz20181223 : 公交真好van,我也要开车\sout\texttt{fz20181223 : 公交真好van,我也要开车}

鸣谢

@fz20181223

信息

ID
1033
难度
9
分类
(无)
标签
递交数
25
已通过
2
通过率
8%
被复制
1
上传者

相关

在下列比赛中:

MOI 2021