WC '17 Contest 1 S3 - Crosscountry Canada

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Woburn Challenge 2017-18 Round 1 - Senior Division

There are N (2 \le N \le 1\,000) cities, with M (0 \le M \le
10\,000) roads running amongst them. The i^{th} road connects two different cities A_{i} and B_{i} (1 \le A_{i}, B_{i} \le N), and can be driven along in either direction in C_{i} (1 \le C_{i} \le
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 \le L \le
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 \le
R_{i} \le 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 \le T \le 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.


In test cases worth 7/28 of the points, L = 1 and C_{i} = 1 (for i
= 1\ldots M).
In test cases worth another 10/28 of the points, C_{i} = 1 (for i =
1\ldots M).

Input Specification

The first line of input consists of four space-separated integers, N, M, L, and T.
The next line consists of integers, R_{1\ldots 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\ldots M.

Output Specification

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


Sample Input 2

2 1 10 1
1 1
2 1 11

Sample Output 2


Sample Explanation 2

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

1 \to 4 (6 mins) Stop at Tim Horton's (3 mins) 4 \to 2 (2 mins) 2 \to 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.


There are no comments at the moment.