湫湫系列故事——过年回家
湫湫系列故事——过年回家
发布时间： 11:54:13
编辑：www.fx114.net
本篇文章主要介绍了"湫湫系列故事——过年回家"，主要涉及到湫湫系列故事——过年回家方面的内容，对于湫湫系列故事——过年回家感兴趣的同学可以参考一下。
Problem Description
　　出门在外，最想念的还是家，对在深圳腾讯工作的HR湫湫来说，春节回家是一年中最期盼的事，不仅可以见到阔别已久的亲人，还能以相亲的名义调侃众多帅哥（她的内心告诉她：如果相亲能遇到参加过腾讯编程马拉松的同学，就直接把自己嫁了~）。
　　同时，每年的春节湫秋也都会纠结一把，因为车票实在是太难抢了，不过2013的春节有点特殊，作为一个曾经的ACMer，湫湫制作出了很完美的刷票机，也就是说她再也不用担心买不上票了，但是想来想去还是觉得随便买票实在是浪费了辛辛苦苦搞出来的刷票机，所以她决定要用最舒适的方式回家。
　　假设湫湫有可能经过的n个城市分别编号从1到n，湫湫要从城市A回到城市B，购票网站上列出了t辆列车行程，每辆车的行程用一个字符串表示，途径的城市间用+号相连，如1+2+3+5代表一辆从1城市分别经过2，3到达5的火车，湫湫可以从中间任意一站出发和下车（路径是单向的，即必须沿字符串从左到右来走），每个字符串对应着一个整数k，k=0表示该车只有硬座，k=1表示该车有卧铺也有硬座，在整个回家的计划中，同一辆车可以坐无限次，为了中途换车的方便，如果在起点坐的是卧铺，则后面乘坐的车必须全是卧铺，同样的，如果在起点坐的是硬座，则后面乘坐的车必须全是硬座，假设一段（一辆车行程中，两相邻城市间为一段）硬座的不舒适度是D1，一段卧铺的不舒适度是D2，求湫湫回家最小的不舒适度。
　　输入数据的第一行包含一个整数Q，表示测试数据的组数；
　　每组数据的第一行是2个正整数n和t，分别表示城市数和列车数；
　　接下来t行，每行一个字符串表示列车行程，字符串长度小于10000，每个字符串后跟一个整数k（k为0或1），之间用空格隔开；
　　接下来一行是D1，D2，其含义见题目描述；
　　最后一行是2个正整数A和B，表示起始和终点城市。
　　[Technical Specification]
　　1 &= Q &= 100
　　1 & n &= 200
　　1 & t &= 1000
　　0 & D1 &= 10000, 0 & D2 &= 10000，D1和D2的大小关系不确定
　　1 &= A, B &= n 且 A && B
　　对于每组数据，如果湫湫可以到达目的地，则输出一个整数，表示湫湫到家所需的最小不舒适度。如果不能到达则直接输出-1。
Sample Input
2+4+3+5+1+6 1
5+4+2+3+1 1
3+2+5+1+6 1
6+3+1+4+5+2 0
Sample Output
2013腾讯编程马拉松初赛第四场（3月24日） &
转载地址：http://acm./showproblem.php?pid=4522
一、不得利用本站危害国家安全、泄露国家秘密，不得侵犯国家社会集体的和公民的合法权益，不得利用本站制作、复制和传播不法有害信息！
二、互相尊重，对自己的言论和行为负责。
本文标题：
本页链接：}