### 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`(1 ≤

_{i}`A`,

_{i}`B`≤

_{i}`N`), and can be driven along in either direction in

`C`(1 ≤

_{i}`C`≤ 100) minutes. There may be multiple roads running directly between any given pair of cities.

_{i}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`= 1, then it does (0 ≤

_{i}`R`≤ 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

_{i}`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`= 1 (for

_{i}`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`, and

_{i}`C`, for

_{i}`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)

It's quiet in here...