New Year's '19 P4 - A Button Challenge

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Santa has visited, and you have found a new video game under your Christmas tree!

In this video game, the player attempts to collect stars scattered around the game world. After collecting a single star, they return to the starting location until all stars have been collected. Moving around requires various manipulating various buttons on the controller, including the A button. What is the minimum number of times the A button must be pressed in order to collect all the stars and beat the game?

The game world consists of N locations numbered from 1 to N. There are s_i stars at location i. Location 1 is the starting location where the player starts the game, and is returned to after collecting a star. There are M known techniques for going from one location to another, these are numbered from 1 to M. The i^\text{th} of these techniques is for going from location a_i to location b_i. These techniques each have different requirements regarding the A button that will be specified in more detail later.

The A button has two states: pressed, and unpressed. Initially, the button is unpressed. Going from the unpressed state to the pressed state is called "pressing the A button". The number of these A presses is the quantity we want to minimize. Note that once the A button is pressed, it does not need to be released right away. The A button can continue to be held even while collecting a star and returning to the starting location.

Each technique has a type t_i which is either A, B, or C.

  • Type A techniques require performing an additional x_i A presses.
  • Type B techniques require performing an additional x_i A presses under the condition that the A button is already being held (in real-life applications, this extra requirement is known as a "half" A press).
  • Type C techniques simply require the A button to be in the unpressed state.

Note that the A button can be manipulated even outside of these techniques - while at one of the N locations the button can be pressed or released at any time.

Constraints

1 \le N, M \le 10^5

0 \le s_i \le 10^5

1 \le a_i, b_i \le N

t_i is either A, B, or C.

0 \le x_i \le 100

It is guaranteed that it is possible to collect all the stars.

Subtask 1 [50%]

There are no type C techniques.

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains two space-separated integers N and M.

The next line contains N space-separated integers s_i.

The next M lines first contain a_i, b_i, and t_i. If t_i is A or B, then the line also contains x_i.

Output Specification

Output a single integer, the minimum number of A presses needed for collecting all stars.

Sample Input

3 3
0 0 5
1 2 B 0
2 3 C
1 3 A 1

Output for Sample Input

3

Explanation for Sample Output

First, press the A button to travel from 1 to 3 and keep it down. After collecting a star, you are returned to 1 with the A button down. The B technique can then be used to travel to 2. Letting go of the A button allows the C technique, which moves you to 3 and after collecting a second star, back to 1. Repeating this process twice lets you go to 3 enough times to collect all the stars. In total, 3 button presses are made.


Comments

There are no comments at the moment.