PEG Judge - WC16 #4 - Pawpsicles

Woburn Challenge 2016-17 Round 4 - Senior Division

Problem 2: Pawpsicles

"All right, slick Nick, you're under arrest."
"Really, for what?"
"Gee, I don't know. How about selling food without a permit, transporting undeclared commerce across borough lines, false advertising…"
"Here: Permit, receipt of declared commerce, and I did not falsely advertise anything. Take care."
"You told that mouse the pawpsicle sticks were redwood!"
"That's right. Red wood. With a space in the middle. Wood that is red."

Nick Wilde has got quite the clever money-making scheme going on. Every day, he…

Heads to an ice cream parlor, purchases a "Jumbo Pop" popsicle (unless he can hustle someone else into purchasing it for him), and melts it down into a sugary liquid.
Transports it to Zootopia's Tundratown district, makes paw prints in a snowy field, fills them with the popsicle liquid, places a popsicle stick in each one, and waits for the resulting "Pawpsicles" to solidify.
Sets up a sales booth outside a lemming bank just in time for the end of the workday, and sells his Pawpsicles to the lemmings as they leave the bank, collecting the discarded popsicle sticks.
Delivers the popsicle sticks to a miniature construction site in Little Rodentia, passing it off as lumber.

By following this sequence of steps, Nick is able to pull in a handsome profit of $200 every day. And the whole operation is perfectly legal! (Well, he may be failing to record his income on his tax returns, but that's besides the point.)

Still, time is money, so Nick's wondering if he's going about things as efficiently as possible. After all, Zootopia's a big place, so studying its map more carefully may suggest some improvements to his daily route.

Zootopia has N (1 ≤ N ≤ 100,000) key locations, with M (0 ≤ M ≤ 100,000) roads running amongst them. The i-th road runs between distinct locations A_i and B_i (1 ≤ A_i, B_i ≤ N), and can be travelled along in either direction in C_i (1 ≤ C_i ≤ 100) minutes. No pair of locations are directly connected by multiple roads.

For Nick's purposes, he's classified each location i with a type T_i (0 ≤ T_i ≤ 4). He has no interest in type-0 locations, but the other 4 location types correspond to the 4 steps of his Pawpsicle operation. Specifically, type-1 locations are ice cream parlors, type-2 locations are fields in Tundratown, type-3 locations are lemming banks, and type-4 locations are construction sites in Little Rodentia.

Nick starts each day in location 1, and needs to travel along a sequence of roads to visit a sequence of locations such that, at some point, he visits a type-1 location, then visits a type-2 location sometime later, then visits a type-3 location sometime after that, and finally visits a type-4 location sometime after that. He's considered to initially visit location 1, and on his way, he may travel through any locations as many times as he'd like.

In order to optimize the efficiency of his Pawpsicle operation, Nick would like to determine the minimum amount of time in which he can complete a route which visits the 4 useful types of locations in the required order. Unfortunately, it may also turn out that no such route exists, in which case Nick may need to consider making a more honest living…

In test cases worth 10/20 of the points, N ≤ 200.

Input Format

The first line of input consists of two space-separated integers N and M.
N lines follow, the i-th of which consists of a single integer T_i (for i = 1..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..M).

Output Format

Output one line consisting of a single integer – the minimum number of minutes required for Nick to complete his Pawpsicle operation, or −1 if it can't be done.

Sample Input

9 9
2 0 0 1 2 3 4 4 3
1 4 9
4 2 3
2 1 4
5 4 1
5 6 4
7 2 9
3 1 2
3 7 3
3 9 4

Sample Output

Sample Explanation

One optimal route which Nick can take is as follows (with the 4 locations at which he'll carry out the steps of his Pawpsicle operator indicated with an asterisk "*"):

1 → 2 → 4* → 2 → 1* → 3 → 9* → 3 → 7*

This route will take 4 + 3 + 3 + 4 + 2 + 4 + 4 + 3 = 27 minutes to complete.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Apr 09, 2017
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3