QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[+3]
统计

列车必将驶向下一站,而舞台将前往何处?你们又将前往何处?

在此刻,你扮演着「观众」 ,n 位舞台少女的人生因你所选择的「命运」 而交织在一起。

为了方便理解,我们用一个三元组 (u,v,w) 来描述一条连接编号为 u,v 的舞台少女,羁绊值为 w 的「命运」。

可是,舞台少女的「命运」并不完全被你所掌握。编号为 s 的舞台少女 Karen 酱,支配着与她自己有关的「命运」。具体地,若一条「命运」(u,v,w) 满足 u=sv=s ,则这条「命运」被 Karen 酱支配着。被 Karen 酱支配的「命运」你无权干涉。而其余的「命运」则可供你自由支配。

你将从你所支配的「命运」中选择 a 条出来( a 是一个由你选择的非负整数),而 Karen 酱则必须选择恰好 k 条与她有关的「命运」。然后,演出开始。

我们称两位舞台少女的人生是有交集的,当且仅当她们被「命运」直接或间接地连接着。

Karen 酱不喜欢无意义的「命运」,所以她要求自己不能与同一个人直接连接着多条「命运」; Karen 酱也不希望看见大家渐行渐远,所以她要求所有 n 位舞台少 女的人生都相互有交集,否则将会罢演。

设最终选择的 a+k 条「命运」的羁绊值所构成的集合为 A ,定义 A 的颠沛值为:

a+ki=1maxi(A)×(109+7)i

其中 maxi(A) 表示集合 A 中第 i 大的数。 「观众」和舞台少女密不可分,现在你需要和 Karen 酱合作,一同献上颠沛值最小的演出。为了方便,你只需要输出你们最终选择的「命运」的羁绊值之和。 若不存在满足 Karen 酱要求的演出,则输出 nonnondayo

形式化题意

给定 m 条边,你需要选出若干条边满足图联通并且编号为 s 的点度数恰为 k。并且与 s 有关的边不能选择重边。找到一种上述式子最小的方案并输出选择的边权和。 无解输出 nonnondayo

输入格式

第一行四个整数 n,m,k,s

接下来 m 行,每行三个整数 u,v,w 表示一条「命运」。

输出格式

一行一个整数表示你们最终选择的「命运」的羁绊值之和,不存在方案则输出 nonnondayo

样例 1

input

4 4 2 1
1 2 1
1 3 2
3 4 3
1 4 4

output

6

数据范围

对于所有数据满足 1k<n5×104m5×105,w109。有重边无自环,wi 互不相同。

  • 子任务 1(5 分):m=n1
  • 子任务 2(10 分):n,m21
  • 子任务 3(15 分):n1000m3×103
  • 子任务 4(20 分):保证去掉编号为 s 的点和与 s 有关的边后,剩下的图为森林。
  • 子任务 5(10 分):满足恰有 k 条边 (ui,vi) 满足其中一个端点为 s&ZeroWidthSpace; 。
  • 子任务 6(20 分):n104m105
  • 子任务 7(20 分):n5×104m5×105