P3686 [CERC2016]爵士之旅 Jazz Journey

    • 5通过
    • 130提交
  • 题目提供者Claris
  • 标签 动态规划,动规,dp
  • 难度 尚无评定
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

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

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

    一共有两种可以购买的机票:

    1.从a到b的单程票,每张只能从a飞到b一次,但不能从b飞到a。

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

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

    输入输出格式

    输入格式:

    第一行包含两个正整数n,d(2<=n,d<=300000),分别表示城市的个数和巡演的次数。

    第二行包含d个正整数a_1,a_2,...,a_d(1<=a_i<=n,a_i!=a_{i+1},a_1=a_d),依次表示巡演计划中每一场所在的城市。

    接下来一行包含一个正整数m(3<=m<=300000),表示机票的种类数。

    接下来m行,每行首先是两个正整数s_i,d_i(1<=s_i,d_i<=n,s_i!=d_i),分别表示起点与终点;接下来一个字符t_i,表示机票的类型,其中“O”表示单程票,“R”表示双程票;最后是一个正整数p_i(1<=p_i<=10^9),表示票价。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    2 5
    1 2 1 2 1
    4
    1 2 R 6
    1 2 O 3
    2 1 O 3
    1 2 R 5
    输出样例#1: 复制
    10
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。