(You may consider jumping to the Input section.)
On a particularly hot day in the month of September of year of 20–, I received a letter from my old acquaintance Dr. —, Professor at the Monotechnical University. It was uncommon for him to resort to these means of communication, and the contents of the letter caused me even greater distress. After many years of suspicion fed by rumors and conversations he was not supposed to overhear, he claimed to have found proof of something of the utmost severity concerning our shared alma mater, and instated me to pay him a visit at his office as soon as possible so we could discuss the matter in private. The ominous feeling that the letter planted on me was nothing but multiplied when, guided by the janitor along the colored corridors of the department buildings, we opened the office only to find a toppled chair, drawers and cupboards open, books and papers scattered on the floor—and no sign of the Professor.
However, as soon as the janitor left to warn the corresponding authorities, I swiftly moved next to the desk and pressed the exact location my correspondent had confided to me in a previous encounter. An hidden drawer opened, and there I found a worn-out notebook with a leather cover and a red elastic band wrapped around it. I knew whoever had searched the office and was behind my colleague’s disappearance was certainly looking for this. A few hours later, in a shabby touristic apartment in a seaside neighborhood, I started reading the document, illuminated by candlelight and accompanied by the roar of waves in the sea and the shouts of shirtless drunkards in the street.
However, I was extremely naive to believe my actions of the day had gone unnoticed. Shortly after I laid myself on bed to relieve the pain behind my eyes, the door opened violently. Following a brief fight in the dark, an impact on my head left me unconscious. When I regained awareness, I was in a poorly lit room from which multiple corridors spawned—a labyrinth. Aching and dizzy, I incorporated myself and approached the walls. I then half saw, half sensed with my fingertips, the etchings on the plaster. One reported “I hear the steps coming closer every minute”, whereas another student lamented “Now I can only beg the Salvataur to spare my life”, and a third one regretted “I wish I had asked to review that Algorithmics test’s grading”. The realization of my doom sank in: I fell to my knees, and started sobbing and hitting the writing with my fist, until pain and frustration made me collapse on the floor.
After a few minutes, I stood up and started to explore the labyrinth of the Salvataur: hopelessly, without the knowledge of which room that I entered would be my last…
Input
Input consists of several cases. Each case starts with the number of vertices 3 ≤ V ≤ 104 and edges 3 ≤ E ≤ 5V in the labyrinth’s graph, the number of vertices 3 ≤ R ≤ 1000 in the human’s route, and a real number, the sense of smell 0 ≤ S ≤ 1 of the Salvataur. Next come E pairs ui vi, one for each edge of the graph, which is undirected and connected. Finally come R vertices 0 ≤ ri < V describing the route of the human. Assume that the vertices are numbered from 0, that there are no repeated edges nor edges with ui = vi, that r0 = 0, and that for all 0 < i < R, either ri−1 = ri, or there is an edge between ri−1 and ri.
At time t = 0, the human is at vertex 0 and the Salvataur at V − 1. For t ≥ 1, they move in turns, starting with the human:
The input is such that the human has a non-zero probability of surviving after R−2 steps.
Output
For each case, print the probability that the Salvataur catches the human in the last round, given the information that it has not caught the human in any of its preceding moves. That probability must include the human moving to rR−1 and finding the Salvataur there, and also the Salvataur making its last move to rR−1. Print the probabilities rounded to a percentage with no decimal figures. The input cases have no precision issues.
Input
3 3 6 1.0 0 1 1 2 2 0 0 1 2 0 1 2 3 3 6 0.5 0 1 1 2 2 0 0 1 2 0 1 2 3 3 6 0.0 0 1 1 2 2 0 0 1 2 0 1 2 3 3 6 0.5 0 1 1 2 2 0 0 1 2 0 1 1 3 3 6 0.5 0 1 1 2 2 0 0 1 2 0 1 0 4 6 5 0.5 0 1 0 2 0 3 1 2 1 3 2 3 0 1 2 3 0 4 6 5 0.0 0 1 0 2 0 3 1 2 1 3 2 3 0 1 2 3 0 4 5 5 0.4 0 1 0 2 0 3 1 2 2 3 0 1 2 3 0 4 5 5 0.0 0 1 0 2 0 3 1 2 2 3 0 1 2 3 0
Output
0% 25% 50% 75% 100% 33% 67% 44% 67%