Task 4 was revealed 3.4.2025 at 18:00 CET
Login required
*
Available from 03.04.2025 18:00 CET until 04.04.2025 17:59 CET - You can get 4 points
Bike Path in Valencia During Las Fallas
Every year in Valencia, the Las Fallas festival brings beautiful sculptures and fireworks - but also causes temporary street closures across the city. You're using a bike-sharing system and want to find the shortest route from station 1 to station N, avoiding roads that are closed during your journey.
City Details:
- There are N bike stations and M roads.
- Each road is bidirectional and takes a specific number of minutes to travel.
- Some roads are closed during specific time intervals (in minutes after midnight).
- You start your trip at station 1 at time T (in minutes after midnight).
Rules:
- If a road is closed at your intended time of travel, you must wait until it reopens.
- There is no upper limit on waiting, but your goal is to minimize total arrival time.
- You may pass through the same station more than once.
Input Format:
N M T
u1 v1 t1 k1 s11 e11 s12 e12 ...
...
uM vM tM kM sM1 eM1 ...
Where:
- N - number of stations (2 <= N <= 1000)
- M - number of roads
- T - starting time (0 <= T < 1440)
- Each road connects stations ui and vi, takes ti minutes to travel
- ki - number of closure intervals for that road
- Each interval [s, e) defines a closed time period (inclusive of s, exclusive of e)
Output Format:
A single integer: the minimum arrival time at station N starting from station 1 at time T, or -1 if it's impossible to reach.
Example Input:
5 5 100
1 2 20 1 110 130
2 3 15 0
3 5 30 1 120 150
1 4 25 0
4 5 20 0
Example Output:
145
Explanation:
- Start at station 1 at time 100
- Travel: 1 → 4 (25 min) → arrive at 125
-
Travel: 4 → 5 (20 min) → arrive at 145
(No closures on these roads)
Even though 1 → 2 is shorter, the closure from 110 to 130 would force a wait.
Your task:
Read input file and into the field with the answer, enter:
- the resulting values
- the country, which the story refers to
- at the end paste the source code of your program.
Click here to download CGW Task 4 Input file
Answer:
Spain
# Set 1 Output
145
# Set 2 Output
90
# Set 3 Output
90
# Set 4 Output
305
# Set 5 Output
145
# Set 6 Output
105
Scoring system:
|
Points for |
Correct answer |
Country |
Source Code |
|
Round 1 |
1 |
1 |
1 |
|
Round 2 |
2 |
1 |
1 |
|
Round 3 |
3 |
1 |
1 |
|
Round 4 |
4 |
1 |
1 |
|
Round 5 |
5 |
1 |
1 |
|
Bonus points for |
Quick and correct answer |
||||||||
|
Round 1 |
5 |
4 |
3 |
2 |
1 |
||||
|
Round 2 |
6 |
5 |
4 |
3 |
2 |
1 |
|||
|
Round 3 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
||
|
Round 4 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
|
|
Round 5 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |