QCC P5 - Vaccine Delivery

View as PDF

Submit solution

Points: 12
Time limit: 2.0s
Python 8.0s
Memory limit: 256M
Python 512M

Author:
Problem types

Having developed a COVID-19 vaccine, CodeVax gives you one final assignment: Deliver the CodeVax vaccine to cities around the world.

More specifically, the planet Earth has a radius of R and a centre at (0,0,0). There are N cities numbered from 1 to N on Earth's surface. Additionally, there are M bidirectional roads connecting cities together. The distance between two cities a b is defined as the shortest distance between the two points by travelling on the surface of planet Earth. Each city has v_i active COVID-19 cases. Furthermore, of the N cities, only K of them have airports. You start in city 1 and can travel along roads at 1 unit per second.

Wanting to help the most people, you decide you will deliver the CodeVax vaccines to the city with the highest number of active COVID-19 cases you can reach, while still getting to an airport strictly before T seconds. Output the number of active COVID-19 cases of such a city or -1 if you can't reach an airport under T seconds.

Input Specification

The first line of input will contain the positive integers N, M, R, T, and K.

The next line will contain K integers, denoting which of the N cities contain an airport to take you home.

The next N lines will contain the integer v_i and the numbers x_i, y_i, z_i, the number of active COVID-19 cases and the coordinates of the ith city. The coordinates of each city will be rounded up to ten decimal places.

The next M lines will contain two integers a and b, meaning there is a bidirectional road between cities a and b.

Output Specification

Output the number of active COVID-19 cases of the most infected city you can reach while reaching a city that has an airport. If you are unable to reach any airport strictly before T seconds, print -1.

Constraints

1 \le N \le 10^5

1 \le M, R \le 10^6

0 \le T, v_i \le 10^9

1 \le K, K_i \le N

1 \le a, b \le N

You may visit any road and/or city multiple times. All K_i are distinct. Not all roads are guaranteed to be distinct. It is guaranteed that the cities will lie on the Earth's surface to within an absolute error of less than 10^{-3}.

Sample Input 1

3 3 3 7 2
2 3
0 -2.5000000000 0.0000000000 1.6583123952
1 1.5000000000 2.0000000000 1.6583123952
2 0.0000000000 0.0000000000 -3.0000000000
1 2
2 3
1 3

Sample Output 1

2

Explanation for Sample 1

You can travel directly to city 3 and deliver the vaccines there in under 7 seconds. From there, you can leave through the airport at city 3.

Sample Input 2

3 3 3 6 2
2 3
0 -2.5000000000 0.0000000000 1.6583123952
1 1.5000000000 2.0000000000 1.6583123952
2 0.0000000000 0.0000000000 -3.0000000000
1 2
2 3
1 3

Sample Output 2

1

Explanation for Sample 2

You cannot travel to city 3 in under 6 seconds. Therefore you must head to city 2, deliver the vaccines there, and leave through the airport at city 2.


Comments

There are no comments at the moment.