Woburn Challenge 2017-18 Round 1 - Senior Division

Problem 3: Crosscountry Canada

There are N (2 ≤ N ≤ 1000) cities, with M (0 ≤ M ≤ 10,000) roads running amongst them. The i-th road connects two different cities A_i and B_i (1 ≤ A_i, B_i ≤ N), and can be driven along in either direction in C_i (1 ≤ C_i ≤ 100) minutes. There may be multiple roads running directly between any given pair of cities.

You're taking a roadtrip across Canada from city 1 to city N. You'd like to reach your destination in as little time as possible, by following a sequence of roads from city to city. However, as every Canadian knows, Tim Horton's pit stops are an essential part of any trip. It's vital that you stop at a Tim Horton's every L (1 ≤ L ≤ 100) minutes or less. In particular, you must never spend strictly more than L consecutive minutes during your trip outside of Tim Hortons' establishments, not counting any time before you leave city 1 or after you arrive at city N.

Somehow, not every city has a Tim Horton's! If R_i = 0, then the i-th city doesn't have one, and if R_i = 1, then it does (0 ≤ R_i ≤ 1). Whenever you arrive in a city which has a Tim Horton's, you may choose to stop at it before continuing on your trip, which takes T (1 ≤ T ≤ 100) minutes.

What's the minimum amount of time required to reach city N from city 1 without ever spending more than L consecutive minutes outside of Tim Horton's establishments? If it can't be done, output -1 instead.

Subtasks

In test cases worth 7/28 of the points, L = 1 and C_i = 1 (for i = 1..M).
In test cases worth another 10/28 of the points, C_i = 1 (for i = 1..M).

Input Format

The first line of input consists of four space-separated integers, N, M, L, and T.
The next line consists of integers, R_1..N.
M lines follow, the i-th of which consists of three space-separated integers, A_i, B_i, and C_i, for i = 1..M.

Output Format

Output a single integer, the minimum amount of time required to validly reach city N from city 1, or -1 if it's impossible.

Sample Input 1

6 10 6 3
0 1 0 1 0 0
1 3 3
1 4 6
1 4 7
2 4 2
2 5 4
2 6 3
3 4 6
4 5 1
4 6 6
5 6 5

Sample Output 1

14

Sample Input 2

2 1 10 1
1 1
2 1 11

Sample Output 2

-1

Sample Explanation 2

In the first case, one optimal route is as follows:

1 → 4 (6 mins) Stop at Tim Horton's (3 mins) 4 → 2 (2 mins) 2 → 6 (3 mins)

In the second case, the single road between the cities is just too long for the trip to be possible, as driving along it would result in a lack of Tim Horton's for more than 10 minutes.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Jan 26, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)