bzoj#P4795. [CERC2016] Jazz Journey
[CERC2016] Jazz Journey
题目描述
Ivan 正在为他的爵士乐队计划一场规模盛大的欧洲巡演。在欧洲一共有 个城市,编号依次为 到 。Ivan计划举办 场演出,分别在城市 ,并且严格遵循这个顺序,而且不会在同一个城市连续巡演两次(即 ),但在整个过程中,他可能在一个城市巡演多次。最终,他一定会回到开始的城市进行巡演(即 )。
Ivan 每次总是选择搭乘一趟从 到 的直达航班。然而,他希望变得聪明一些,尽量节省机票的开支。你也知道,机票的价格取决于供给和需求,比如一张单程票可能会比相同目的地的双程票还要贵。一共有两种可以购买的机票:
-
从 到 的单程票,每张只能从 飞到 一次,但不能从 飞到 。
-
从 到 的双程票,只需购买一张,就能从 飞到 一次,然后从 飞回 一次,但先从 飞回 是不允许的。 当然,你也可以选择从 飞到 之后就再也不返回 。
给定可以购买的机票集合,每种机票都是无限量供应的。请帮助 Ivan 找到一种最省钱的方案。你可以认为合法方案必然存在。
输入格式
第一行包含两个正整数 ,分别表示城市的个数和巡演的次数。
第二行包含 个正整数 ,依次表示巡演计划中每一场所在的城市。
接下来一行包含一个正整数 ,表示机票的种类数。
接下来 行,每行首先是两个正整数 ,分别表示起点与终点;接下来一个字符 ,表示机票的类型,其中 O
表示单程票,R
表示双程票;最后是一个正整数 ,表示票价。
输出格式
输出一行一个整数,即完成巡演所需支付的最小机票总费用。
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
数据规模与约定
对于 的数据,,,,,,,,。