bzoj#P4795. [CERC2016] Jazz Journey

[CERC2016] Jazz Journey

题目描述

Ivan 正在为他的爵士乐队计划一场规模盛大的欧洲巡演。在欧洲一共有 nn 个城市,编号依次为 11nn。Ivan计划举办 dd 场演出,分别在城市 a1,a2,,ada_1,a_2,\cdots,a_d,并且严格遵循这个顺序,而且不会在同一个城市连续巡演两次(即 aiai+1a_i\neq a_{i+1}),但在整个过程中,他可能在一个城市巡演多次。最终,他一定会回到开始的城市进行巡演(即 a1=ada_1=a_d)。

Ivan 每次总是选择搭乘一趟从 aia_iai+1a_{i+1} 的直达航班。然而,他希望变得聪明一些,尽量节省机票的开支。你也知道,机票的价格取决于供给和需求,比如一张单程票可能会比相同目的地的双程票还要贵。一共有两种可以购买的机票:

  1. aabb 的单程票,每张只能从 aa 飞到 bb 一次,但不能从 bb 飞到 aa

  2. aabb 的双程票,只需购买一张,就能从 aa 飞到 bb 一次,然后从 bb 飞回 aa 一次,但先从 bb 飞回 aa 是不允许的。 当然,你也可以选择从 aa 飞到 bb 之后就再也不返回 aa

给定可以购买的机票集合,每种机票都是无限量供应的。请帮助 Ivan 找到一种最省钱的方案。你可以认为合法方案必然存在。

输入格式

第一行包含两个正整数 n,dn,d,分别表示城市的个数和巡演的次数。
第二行包含 dd 个正整数 a1,a2,,ada_1,a_2,\cdots,a_d,依次表示巡演计划中每一场所在的城市。
接下来一行包含一个正整数 mm,表示机票的种类数。
接下来 mm 行,每行首先是两个正整数 si,dis_i,d_i,分别表示起点与终点;接下来一个字符 tit_i,表示机票的类型,其中 O 表示单程票,R 表示双程票;最后是一个正整数 pip_i,表示票价。

输出格式

输出一行一个整数,即完成巡演所需支付的最小机票总费用。

2 5
1 2 1 2 1
4
1 2 R 6
1 2 O 3
2 1 O 3
1 2 R 5
10

数据规模与约定

对于 100%100\% 的数据,2n,d3×1052\le n,d\le 3\times 10^51ain1\le a_i\le na1=ada_1=a_daiai+1a_i\neq a_{i+1}3m3×1053\le m\le 3\times 10^51si,din1\le s_i,d_i\le nsidis_i\neq d_i1pi1091\le p_i\le 10^9