PID644 / 青青的音乐游戏
题目描述

你在游戏中心玩过Jubeat吗?

虽然这个游戏看上去很复杂的样子,但是其实也不是那么复杂啦——你可以认为他是一个在4*4矩阵上的“打地鼠”游戏。随着音乐的进行,某些格子会浮现一个图标,你需要做的是在图标完全显示出来的时候按下格子,这样你就得到了分数。

当然,如果音乐太快或者同时需要按下的键太多,这个游戏也变得不那么简单了。青青是一个喜欢玩Jubeat的可爱的小孩,不过他的水平可不怎么样,在贡献出自己的所有的零花钱后,他发现自己的水平仍然没有什么进步,该Failed的还是Failed,该C的还是C,于是他决定开发属于自己的Jubeat版本——Jubeat EX!

在Jubeat EX!中,每个时间同时只会出现一个需要按下的图标,而且再也不需要等待图标完全显示了,只需要在规定的时间点按下按键就行。这样游戏难度无疑降低了不少,但是悲剧的是,由于青青的技术原因,他只能使用三根手指来按按键,并且每根手指从某个按键移动到另外一个按键都需要一个特定的体力。青青还小,没有太多的体力,所以请你帮青青计算出完成一首歌最少需要的体力值。

输入格式

输入有多组数据。输入文件的第一行是一个数T(1<=T<=5),表示有T组数据。

每组数据的第一行是一个数N(N<=1000),表示有多少个需要按下的图标。

接下来的N行,每行是两个数Ai,Bi(0<=Ai<=10^9,1<=Bi<=16),表示第i个图标在Ai时间出现,并且出现的格子编号是Bi。[b]为了方便起见,我们可以将4*4的矩阵按从左到右、从上到下的顺序编号为1~16。[/b]

接下来有三组格式相同的输入,都是一个16*16的矩阵,表示三根手指中的某根手指从i格子移动到j格子需要F[i][j]的体力。输入保证F[i][j]=F[j][i],并且F[i][i]=0。矩阵中所有元素小于500。

青青一开始三根手指都放在第一个格子(编号为1的格子)里。

输出格式

对于每组数据输出一个数,表示最小耗费的体力值。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论