0237. Runaway

Имя входного файла:	runaway.in
Имя выходного файла:	runaway.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Damn!... How it can be happened to you – one of the best agents of FBI? You were imprisoned for crime; you were even not able to do. "Spy, traitor, murderer", they said. It sounds banal, but you were tripped up by some secret terroristical organization, and your friends (oh┘ ex-friends, I mean) didn't want to help you. You are alone: and it seems to be no ways to exit. There are only thick lead walls around you. You are in underground prison. Wait: what▓s happening? You hear screams and explosions nearby. What a hell!?... <Darkness over you and you lose consciousness>

You wake up and look around you. Doorlock of your cell is seriously damaged, so you can open the door easily. Wait: what a strange heat? You look into corridor and quickly realize situation. Prison was attacked from air by napalm-bomber. Napalm is still over prison, but it quickly burns its road down. The temperature everywhere in prison is slowly raising, in different parts of prison speed of heating is not the same, but everywhere it is non-negative value. You know, that corridors of a prison have toral shape. It was offered by D. Kurov scientist just to check his geometry skills. But it does not matter to you, and the only thing, important to you now, is that there are several exits from this prison. Fortunately, you know the map of prison (it is on the wall of corridor, marked as "Evacuation Plan"). Also you know the approximate points of falling napalm bombs (you heard that information in moment of losing consciousness from internal prison communicator), so you can predict speeds of heat growing for all corridors. You have already got evacuation fire-resistant suit which can resist heat of H degrees Centigrade (if temperature is greater than H, your character will die). You must construct a way to get out from prison in such a manner such that maximal heat of your suit on this way is minimal possible (temperature of suit is always equal to current temperature in corridor).

Prison consists of M corridors and N corridor junctions. Also E of N junctions are exits, and you are initially located at junction number S (junctions are numbered from 1 to N). Corridors have their initial heat R_i, and non-negative speed of heat raising P_i (in degrees by second), also corridors have lengths T_i – time you need to run over them (in seconds). You must consider that junctions always have temperature 0.

Input file

On first line of input file there are only numbers N, M, H, S and E (1 ≤ N ≤ 100; 1 ≤ S,E ≤ N; 1 ≤ M,H ≤ 10000). Next M lines describe prison corridors, I-th line of them containing numbers A_i, B_i, T_i, R_i and P_i, where A and B are numbers of junctions, connected by corresponding corridor (1 ≤ A_i,B_i ≤ N; 1 ≤ T_i ≤ 10000; 0 ≤ R_i,P_i ≤ 10000; A_i ≠ B_i). At next line there are exactly E numbers F_i – numbers of junctions, which are exits (1 ≤ F_i ≤ N). There are no multiple corridors between any two junctions. All corridors are two-sided. All numbers are integers.

Output file

On the first line must be exactly one word "YES" (if you can stay alive and get out from prison) or "NO" (in other case). In case of positive answer, second line of output file must contain maximal heat of suit on the best way, then on the third line there must be the best way itself (if there are many best ways, you can output any one of them) in form: Z – number of junctions in the way, then Z numbers – numbers of junctions in best way in order of passing it (start junction assumed to be passed, even if you make no moves).

Example:

runaway.in	runaway.out
3 4 10 4 1 1 2 1 0 1 1 3 2 1 0 1 4 3 0 1 2 3 4 2 2 3	YES 3 3 4 1 3

Источник: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Обсудить       Отправить решение



Версия для печати