OpenJudge

06:哈利波特与魔法石

总时间限制:
1000ms
内存限制:
131000kB
描述

  大年初三的那个晚上,小可可去电影院看了《哈利·波特与魔法石》,回到家坐在椅子上不一会儿就睡着了,并且梦见自己成了哈利·波特驰骋在充满了正义与邪恶的宇宙中执著地为了正义而战。

  那天哈利·波特去拯救Super Samuel星球上的生灵。该星球上有七种不同的地形,依次分别是石子路、森林、草地、山地、雪地、沼泽和沙漠,用数字17来表示。任意两个城市之间都存在至少一条通路,而且任意两个能够不经过别的城市而直接通达的城市ij之间都只存在一种地形ti,j 奇怪的是,在Super Samuel星球上哈利·波特穿越地形u所需时间与该地形的区域大小无关,却与地形u的区域中是否有魔法石有关。如果地形u的区域中没有魔法石,哈利·波特要花hu的时间才能穿越该地区,否则他只要花一半的时间就能穿越了。已知h12h26h34h48h56h610h714su1表示地形u的区域中有魔法石;su0表示地形u的区域中没有魔法石。


  例如,如上图所示,有4对可以直接通达的城市(城市121324以及34);s10s21s3s4s5s6s70即只有森林中有魔法石,因此穿越森林所花费的时间是6/23,穿越石子路和草地的时间仍然分别是24,如果哈利·波特想从城市1到达城市4,则最快的路线是经过城市2,这条路线需要的时间是235

  哈利·波特总是忙于铲除邪恶、伸张正义,没有时间去寻找从起点城市i到终点城市j之间的最快路线。现在聘你作为哈利·波特的助手编写程序寻找最快路线为哈利·波特腾出更多的时间来将正义事业进行到底。


输入
第一行有七个数,分别是s1、s2、……、s7 ;
第二行有两个数,依次分别是起点城市i和终点城市j ;
第三行有一个正整数C (C≤10000),表示随后的C行中每行存放了一对能直接通达的城市的信息。能直接通达的城市的信息由三个数组成,依次分别是两个城市的编号和这两个城市之间的地形。城市的编号都是不超过100的正整数,但是各个城市的编号未必连续。
同一行中相邻的两个数都是用一个空白字符隔开的。
输出
以一行的形式输出起点城市i和终点城市j之间的最快路线所需要的时间。
样例输入
0 1 0 0 0 0 0
1 4
4
1 2 1
1 3 1
2 4 2
3 4 3
样例输出
5
来源
曙光奥赛
全局题号
13290
提交次数
29
尝试人数
9
通过人数
5