TLE '16 Contest 1 P4 - Microwaves Again!

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 3.0s
Python 5.0s
Memory limit: 128M

Problem type

TT1103 thought that the microwave situation at the University of Waterloo would be better than that at Pierre Elliott Trudeau High School, but he was wrong! Microwaves at the Waterloo MC (Mainland China) building are spread all throughout the building, and of course, there is always a line of students waiting to microwave their lunches.

The MC building contains N rooms (numbered from 1 to N), which are connected by M two-way corridors. Each corridor is in the form of u v d (1 \leq u, v \leq N, u \neq v), specifying that a corridor of length d meters connects rooms u and v. For any pair of nodes, there is at most one edge in between them. Additionally, the i^{th} room contains m_i microwaves.

Because of the unbearable circumstances, TT1103 plots to destroy as many microwaves in the MC as he can! He will use a powerful move called the Atomic Blast, which will instantly vaporize any microwave in any room no greater than K meters from the room he currently is in. Assume that room dimensions do not count towards this length.

TT1103 can activate his Atomic Blast move up to 3 times. What is the largest number of microwaves that he can destroy?


1 \leq N \leq 100

0 \leq M \leq \frac{N(N-1)}{2}

0 \leq K \leq 10^8

1 \leq d \leq 10\,000

0 \leq m_i \leq 100

In addition, the following subtasks hold additional constraints:

Subtask 1 [15%]

K = 1

Up to 5 rooms contain at least one microwave.

Subtask 2 [35%]

d = 1

Up to 30 rooms contain at least one microwave.

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line will contain 3 space-separated integers: N, M, and K.

The next line of input will contain N space-separated integers. The i^{th} integer signifies m_i.

M lines of input follow. Each line represents a corridor in the form of u v d.

Output Specification

Output a single integer, the maximum number of microwaves that TT1103 can destroy.

Sample Input

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

Sample Output


Explanation for Sample Output

TT1103 can use his first Atomic Blast in room 1 in order to destroy all microwaves in rooms 1 and 2. He then can use two more Atomic Blasts to destroy separately all microwaves in rooms 3 and 4.


  • 0
    ZQFMGB12  commented on Sept. 21, 2016, 7:53 p.m. edited

    The time limit for Java and Python has been raised to 10 seconds. This change should not affect anybody who have submitted in these languages.

    UPD: Time limit for other submissions have been raised to 5s. Sorry for any inconvenience.