P2494 [SDOI2011] Secrecy

Nowadays, secrecy has become very important and also very difficult. If it is not done well, the consequences can be serious. For example, someone did not repair their computer themselves and did not remove the hard drive—what happened afterward is known to everyone. Of course, the military needs secrecy the most, more than ordinary people. To cope with satellites flying around in the sky, military bases are usually built underground. A certain base in country K is structured as follows: on the ground, there are two rows of large shafts serving as entrances and exits, with a total of $n_1$. Inside, there are many cavities that are mutually disconnected except that they can share entrances. Each cavity has exactly two entrances, and these two entrances are not in the same row. For convenience, the entrances in the two rows are numbered $1, 3, 5, \dots$ and $2, 4, 6, \dots$, and the largest index is $n_1$. Although we have talked so much about secrecy, decryption is also a tangled matter. In fact, the simplest brute-force decryption method is to send someone to have a look... We have elite special forces. If you deploy one unit to some entrance of the base in country K, then all cavities directly connected to that entrance can be explored by that unit, and only those cavities can be explored by that unit. Now you have enough units at your disposal, and you must use them to explore all cavities inside the base in country K. Your base is not too close to the base in country K. You are given a map of the surrounding area, represented by $n$ checkpoints and $m$ roads connecting these points. Points $1$ through $n_1$ are the entrances to the base in country K, and point $n$ is the starting point of your units. For each road, there is a travel time $t$ and a safety factor $s$. Because the intelligence department assessed safety only for one-way roads, these roads are one-way only, and there are no cycles. A unit departs from your base, follows some path, and reaches an entrance of the base in country K. The risk of this unit is defined as the ratio of the total time to the sum of the safety factors of all roads along that path. The overall operation risk is the sum of the risks of all the units you dispatch. You need to explore the entire base in country K while minimizing this value. Hurry up and finish this task before a certain professor in country K declares that you are from country K.

The first line contains two positive integers $n, m$, the number of checkpoints and roads on the map. Each of the next $m$ lines contains four positive integers $a, b, t, s$, indicating a one-way road from $a$ to $b$ with travel time $t$ and safety factor $s$. The next line contains two positive integers $m_1$ and $n_1$, where $m_1$ is the number of cavities in the base in country K, and $n_1$ is the number of entrances. Each of the next $m_1$ lines contains two positive integers $u, v$, indicating the two entrances of each cavity.

Output one line with the minimum total risk, to one decimal place. Output -1 if the task is impossible.

- For 30% of the testdata, $n \leq 30$. - For 60% of the testdata, $n \leq 300$. - For an additional 40% of the testdata, $n_1 \leq 20$. - For 100% of the testdata: $4 \leq n \leq 700$, $m \leq 100000$, $a, b \leq n$, $1 \leq t, s \leq 10$, $m_1 \leq 40000$, $n_1 < \min(n, 161)$, $u, v \leq n_1$, $u$ is odd, and $v$ is even. Translated by ChatGPT 5