## WC '17 Contest 1 S3 - Crosscountry Canada

View as PDF

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

Author:
Problem type
##### Woburn Challenge 2017-18 Round 1 - Senior Division

There are cities, with roads running amongst them. The road connects two different cities and , and can be driven along in either direction in minutes. There may be multiple roads running directly between any given pair of cities.

You're taking a roadtrip across Canada from city to city . 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 minutes or less. In particular, you must never spend strictly more than consecutive minutes during your trip outside of Tim Hortons' establishments, not counting any time before you leave city or after you arrive at city .

Somehow, not every city has a Tim Horton's! If , then the city doesn't have one, and if , then it does . 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 minutes.

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

In test cases worth of the points, and (for ).
In test cases worth another of the points, (for ).

#### Input Specification

The first line of input consists of four space-separated integers, , , , and .
The next line consists of integers, .
lines follow, the of which consists of three space-separated integers, , , and , for .

#### Output Specification

Output a single integer, the minimum amount of time required to validly reach city from city , 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:

( mins) Stop at Tim Horton's ( mins) ( mins) ( 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 minutes.