P3686 [CERC2016] Jazz Journey

Ivan is planning a grand European tour for his jazz band. There are $n$ cities in Europe, labeled $1 \sim n$. Ivan plans to hold $d$ concerts in cities $a_1, a_2, \dots, a_d$ in this exact order, and he will never perform in the same city twice in a row (that is, $a_i \ne a_{i+1}$). However, over the whole tour, he may visit the same city multiple times. In the end, he will return to the starting city to perform (that is, $a_1 = a_d$). Each time, Ivan takes a direct flight from $a_i$ to $a_{i+1}$. He wants to be smart and minimize the total cost of tickets. As you know, prices depend on supply and demand: for example, a one-way ticket might even be more expensive than a round-trip ticket for the same pair of cities. There are two types of tickets available: 1. A one-way ticket from $a$ to $b$, which allows exactly one flight from $a$ to $b$, but not from $b$ to $a$. 2. A round-trip ticket from $a$ to $b$: buying one allows one flight from $a$ to $b$, and then one flight from $b$ back to $a$, but you are not allowed to use it in the reverse order. Of course, you may choose not to fly back after going from $a$ to $b$. You are given the set of available tickets, with unlimited supply of each type. Please help Ivan find the minimum possible total cost. You may assume that at least one valid plan exists.

The first line contains two positive integers $n, d$ ($2 \le n, d \le 3 \times 10^5$), the number of cities and the number of concerts. The second line contains $d$ positive integers $a_1, a_2, \dots, a_d$ ($1 \le a_i \le n, a_i \ne a_{i+1}, a_1 = a_d$), indicating the city of each concert in order. The next line contains a positive integer $m$ ($3 \le m \le 3 \times 10^5$), the number of ticket types. Each of the next $m$ lines contains two positive integers $s_i, d_i$ ($1 \le s_i, d_i \le n, s_i \ne d_i$), the start and end cities; followed by a character $t_i$ indicating the ticket type, where "O" means a one-way ticket and "R" means a round-trip ticket; and finally a positive integer $p_i$ ($1 \le p_i \le 10^9$), the ticket price.

Output a single integer: the minimum total ticket cost to complete the tour.

Translated by ChatGPT 5