Skip to content

11308: 【原1308】东之国的秋获祭

题目

题目描述

author: WaP 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1308

Description

幻想乡的秋季是由两位神灵姐妹掌管的:姐姐秋静叶(Aki Sizuha),掌管红叶程度的能力,妹妹秋穰子(Aki Minoriko),掌管丰收程度的能力。

又到了一年秋天,是两位秋之神活动的时候了。秋静叶会去到各处的阔叶林,依靠她的力量将所有的树叶染成红色,再将红叶变为落叶(但实情似乎是她用脚把树踹得落叶纷纷才对);而秋穰子会来到信仰她之人的农田中,卯足了劲一个一个地使作物发育成熟(因此受到了人们的爱戴,会被人类叫去参加收获祭以表达感谢之意)。在两位神明完成自己的工作后,她们会在一处汇合,一边挖着红薯翻弄着土地,一边眺望着红叶美丽的景致。

整个幻想乡被抽象为一个n个节点m条边的无向图,一开始秋静叶与秋穰子在节点k。现在已知走过每条路所需的时间,p片阔叶林的分布以及信仰秋穰子之人的q片农田位置。由于姐妹俩希望更多地欣赏秋天的美景而不是工作(幻想乡的神明都有点偷懒),因此希望找到最快的路线,使得她们能够尽早地汇合。

另外,有可能存在有些树林和农田无法走到,那么两位神明就会先去那些能走到的树林和农田,而将剩余地方的工作暂时搁置(话说她们不是会飞吗……真是懒散的神明啊)。 ——摘自人间之里寺子屋《式神的程式》考试试题

题人:上白泽慧音(Kamishirasawa Keine)

Input Format

输入至多m+3行。

第一行5个整数n,m,k,p,q,然后是两个正整数s1,s2,表示姐妹两人的移动速度

第二行p个不同的整数,表示秋静叶所要去的阔叶林所处的节点

第三行q个不同的整数,表示信仰秋穰子之人的农田所处的节点

以下m行,每行3个整数x,y,z,表示节点x与节点y之间有一条边,距离为z

输入保证没有自环和重边,并且格式上没有空行

Output Format

第一行一个小数,保留两位小数,表示两位神明能够汇合的最短时间

第二行:若秋静叶还有树林不能到达,则从小到大输出不能走到的树林节点(一个空格隔开),否则输出”NONE”

第三行:若秋穰子还有农田不能到达, 则从小到大输出秋穰子不能走到的农田节点(一个空格隔开),否则输出”NONE”

Sample Input

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

Sample Output

3.00
6
NONE

Sample Illustration

秋静叶走到1或4再走到2,秋穰子先走到1或4再走到3,然后两人在1或4汇合。

秋静叶无法走到6

Hint

40%的数据(Extra):n<=1000, p, q<=6

100%的数据(Phantasm):1<=n<=40000, m<=40000, 0<=p, q<=15, s1, s2<=500, 0<=z<=50000

这里我们认为神明施展神力是不需要时间的,实际上就算给了这个数据又有什么意义呢,反正是很弱的神明(笑)

时限:1.5s

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!