【tyvj1467】通向聚会的道路

2014年3月2日1,1240

背景 Background

Candy住在一个被划分为n个区域的神奇小镇中,其中Candy的家在编号为n的区域,Candy生日这天,大家都急急忙忙赶去Candy家庆祝Candy的生日。

描述 Description

Candy共有t个朋友住在不同的区域。小镇有m条道路,小镇的神奇之处在于其中的p1条道路只会在你走过区域的的个数为奇数时候开启,p2道路只会在你走过区域的个数为偶数的时候开启,剩下的道路一直都会开启。并且,所有的道路只能够单向通过。飘飘乎居士希望知道在所有的好朋友中,谁离Candy最近?。

输入格式 InputFormat

第一行:两个正整数n m,表示共n个区域,m条道路
接下来m行,每行三个正整数u v s表示u到v的单向道路,路程为s,其中第i条道路的编号为i。
接着一个整数p1以及p1个正整数odd[i],表示编号为odd[i]的道路只会在走过奇数个区域时开启。
接着一个整数p2以及p2个正整数even[i],表示编号为even[i]的道路只会在走过偶数个区域时开启。
接下来一个正整数 t
紧接着t行,每行一个正整数h以及一个不超过10个字符长度的字符串na(且均有小写字母组成),表示在h区域居住着名字为na的人。

输出格式 OutputFormat

第一行,即距离candy家最近的人的名字,数据保证有且只有一个人为最后的答案。
第二行,该人到candy家的距离。
如果存在多解,则输入名字中字典序较小的一人。

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

pink尽管从1->3->4距离更近,但因为1->2的这条道路只有在走过奇数个区域时才开启,而pink此时走过的区域为偶数个(0个)(我们规定,出发点不算走第一个区域),所以pink只好沿1—>2—>3—>4,距离为5;
Violethill尽管沿2—>3—>4距离为3,但因为3—>4这条道路只有在走过偶数个区域时才开启,当violethill从2到3时,只走了奇数个(1个)区域,道路不会开启。所以,violethill只好沿2—>4这条道路行走,距离为4,所以violethill比pink更快到candy家中,并且距离为4。
对于30%的数据 0<n<=100
对于100%的数据0<n<=10000   0<m<=100000
对于所有数据保证两区域间的距离<=100000
数据保证运算即结果在maxlongint以内
数据保证输入的正确性,即至少有一个人可以到达candy家中,并且一个区域最多只有一人,不会出现相同名字的人。
友情提示:可能出现有些道路既在odd中出现,也在even中出现。并且odd或者even中的数都可能出现重复数字。

题解参看tyvj,讲的很清楚