Prázdny
Prázdny

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