Woburn Challenge 2015-16 Round 1 - Senior Division

Problem 3: Contest Sites

It's no surprise that the Programming Enrichment Group at Woburn participates in a wide number of programming contests. However, not all contests are held at the same place (worry not – the Woburn Challenge finals will be held at a single location). In fact if too many people register for a contest, the contest organizers may even demand that the same contest be held in two entirely different towns! This will make it a lot harder for our young Woburnites to compete in the contest, but certainly won't stop them from trying.

There are N (2 ≤ N ≤ 10⁵) towns uniquely numbered with integers from 1 to N, and M (1 ≤ M ≤ 10⁵) one-way roads running amongst them. Specifically, the i-th road (for i = 1..M) allows one to travel from a town A_i to a different town B_i (1 ≤ A_i, B_i ≤ N; A ≠ B) and has a distance of D_i (1 ≤ D_i ≤ 100) kilometres. No two roads run between the same pair of towns in the same direction. A very large programming contest is soon to be held across two locations, with the main contest site located in town 1 and the secondary contest site located in town 2. A non-zero number of Woburnites will be competing in this contest, with C_i (0 ≤ C_i ≤ 10⁶) of them living in town i (for each i = 1..N). Each competitor must select one of the two contest sites and travel to it using a sequence of roads. This sequence is possibly empty, if they're fortunate enough to live in the same town as their chosen contest site.

There is a catch! Resources are limited at the second contest site, so the contest organizers have insisted that no more than K (0 ≤ K ≤ 10⁹) of the competitors attend the secondary site (located in town 2). Given that the Woburnites collaborate to come up with the best travel strategy, you must help them determine the minimum total combined distance that they must travel in order to all attend the contest, such that no more than K of them travel to the secondary site.

In test cases worth 60% of the marks, N ≤ 100.
In a subset of those cases worth 30% of the marks, C_i ≤ 1 (for i = 1..N).

Input Format

Line 1 of input will contain three space-separated integers, the values of N, M, and K, respectively representing the number of towns, roads, and the maximum number of Woburnites that may attend the second site.
There will be N lines to follow. The i-th of these lines (for i = 1..N) will contain a single integer C_i, representing the number of Woburnites living in town i.
There will be M lines to follow. The i-th of these lines (for i = 1..M) will contain three space-separated integers, the values of A_i, B_i, and D_i representing the i-th one-way road.

Output Format

The output should consist of a single integer. If it is possible for the Woburnites to travel to all contest sites with no more than K of them attending the secondary site, then output the minimum total combined distance that they must travel to do so. Output -1 if it is impossible for all of them to reach a contest site while satisfying the condition. Please note that the answer may not necessarily fit in a 32-bit integer.

Sample Input

4 5 5
2
1
5
7
1 2 1
3 2 1
3 4 1
4 1 1
4 3 1

Sample Output

13

Explanation

There are 4 towns and 5 roads between them. At most 5 people may attend the second contest site. Each road happens to have a distance of 1. An optimal travel strategy is as follows.

• We let competitors from towns 1 and 2 attend the contest sites at their respective towns (incurring an additional 0 kilometres to our total distance).
• We let all 7 of our competitors from town 4 travel to the main contest site (incurring a total of 7 kilometres).
• We let 4/5 of the competitors from town 3 travel to the secondary contest site (incurring a total of 4 kilometres).
• We let the remaining competitor from town 3 must travel to the main site through town 4 (incurring an additional 2 kilometres to our total distance).

The total distance traveled across all of the competitors is 0 + 7 + 4 + 2 = 13 kilometres.

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 5.00s
Memory Limit: 64M
Added: Oct 17, 2015
Authors: SourSpinach, Alex

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

Comments (Search)

If a contestant can't reach either site, then there is no way to distribute all contestants. The problem statement contains information as to what should be done in this case.