WC '16 Contest 3 S2 - Training Regimen

View as PDF

Submit solution

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

Problem type
Woburn Challenge 2016-17 Round 3 - Senior Division

In the world of Pokémon Navy Green, there are N (2 \le N \le 200\,000) towns, with M (0 \le M \le 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 A_i and B_i (1 \le A_i, B_i \le 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 C_i (1 \le C_i \le 10^9).

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 T_i (1 \le T_i \le 10^9) minutes of training to increase your Pyglion's level by 1. This T_i–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 \le 500, M \le 500, and C_i \le 500.

Input Specification

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, T_i (for i = 1 \dots N).
M lines follow, with the i-th of these lines consisting of three space-separated integers A_i, B_i, and C_i, (for i = 1 \dots M).

Output Specification

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
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


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 4.
  • 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.


There are no comments at the moment.