Woburn Challenge 2016-17 Round 3 - Senior Division

Problem 2: Training Regimen

In the world of Pokémon Navy Green, there are N (2 ≤ N ≤ 200,000) towns, with M (0 ≤ M ≤ 200,000) routes running amongst them. At the beginning of the game, you find yourself in town 1 with a starting Pokémon of your choice – a cute level 1 Pyglion! Your objective is to reach town N by following a sequence of routes.

The i-th route connects distinct towns Ai and Bi (1 ≤ Ai, Bi ≤ N), and can be walked along in either direction. No pair of towns are directly connected by multiple routes. However, the routes are also crawling with dangerous Pokémon. As such, you can only dare venture along the i-th route if your Pyglion's level is currently no smaller than Ci (1 ≤ Ci ≤ 109).

As mentioned, your Pyglion's level is initially 1, but it can be increased through intensive training. Each town has its own training gym for that purpose. However, some gyms are more efficient than others – in particular, in the i-th town, it takes Ti (1 ≤ Ti ≤ 109) minutes of training to increase your Pyglion's level by 1. This Ti–minute process can be repeated as many times as you'd like.

You'd hate to tucker out your poor Pyglion more than necessary, so you'd like to reach town N after spending as little total time training in gyms as possible. Note that time spent walking along routes isn't relevant, and that you may revisit towns on your adventure as often as you'd like. Please determine the minimum number of minutes of training required to reach town N, or determine that you can't complete your trip no matter how much training you put your Pyglion through.

In test cases worth 13/18 of the points, N ≤ 500, M ≤ 500, and Ci ≤ 500.

Input Format

The first line of input consists of two space-separated integers N and M.
N lines follow, with the i-th of these lines consisting of a single integer, Ti (for i = 1..N).
M lines follow, with the i-th of these lines consisting of three space-separated integers Ai, Bi, and Ci, (for i = 1..M).

Output Format

Output one line consisting of a single integer – the minimum number of minutes of training required to reach town N, or –1 if it can't be done.
Note that the answer may not necessarily fit within a 32-bit signed integer (you may need the long long type in C++, or long in Java).

Sample Input

6 8
14
5
8
10
2
4
1 4 5
1 2 8
4 5 12
3 1 2
6 3 11
2 3 14
5 6 4
2 4 6

Sample Output

71

Sample Explanation

One optimal sequence of actions is as follows:

  • Train in town 1 for 14 minutes (up to level 2).
  • Walk to town 3.
  • Train in town 3 for 32 minutes (up to level 6).
  • Walk to town 1.
  • Walk to town 2.
  • Train in town 2 for 25 minutes (up to level 11).
  • Walk to town 1.
  • Walk to town 3.
  • Walk to town 6.

All Submissions
Best Solutions


Point Value: 12 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Feb 19, 2017
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...