#sf1. 拯救大兵瑞恩

拯救大兵瑞恩

题目描述

19441944 年,特种兵麦克接到国防部的命令,要求立即赶赴太平洋上的一个孤岛,营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里,迷宫地形复杂,但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形,其南北方向被划分为 NN 行,东西方向被划分为 MM 列,于是整个迷宫被划分为 N×MN\times M 个单元。每一个单元的位置可用一个有序数对(单元的行号,单元的列号)来表示。南北或东西方向相邻的 22 个单元之间可能互通,也可能有一扇锁着的门,或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙,并且所有的门被分成PP 类,打开同一类的门的钥匙相同,不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角,即 (N,M)(N,M) 单元里,并已经昏迷。迷宫只有一个入口,在西北角。也就是说,麦克可以直接进入 (1,1)(1,1) 单元。另外,麦克从一个单元移动到另一个相邻单元的时间为 11,拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法,帮助麦克以最快的方式到达瑞恩所在单元,营救大兵瑞恩。

输入格式

11 行有 33 个整数,分别表示 N,M,PN,M,P 的值。

22 行是 11 个整数 KK,表示迷宫中门和墙的总数。

I+2I+2(1IK)(1\leq I\leq K),有 55 个整数,依次为Xi1,Yi1,Xi2,Yi2,GiX_{i1},Y_{i1},X_{i2},Y_{i2},G_i

  • Gi1G_i \geq 1 时,表示 (Xi1,Yi1)(X_{i1},Y_{i1}) 单元与 (Xi2,Yi2)(X_{i2},Y_{i2}) 单元之间有一扇第 GiG_i 类的门

  • Gi=0G_i=0 时,表示 (Xi1,Yi1)(X_{i1},Y_{i1}) 单元与 (Xi2,Yi2)(X_{i2},Y_{i2}) 单元之间有一堵不可逾越的墙(其中,Xi1Xi2+Yi1Yi2=1|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=10GiP0\leq G_i\leq P)。

K+3K+3 行是一个整数 SS,表示迷宫中存放的钥匙总数。

K+3+JK+3+J(1JS)(1\leq J\leq S),有 33 个整数,依次为 Xi1,Yi1,QiX_{i1},Y_{i1},Q_i:表示第 JJ 把钥匙存放在 (Xi1,Yi1)(X_{i1},Y_{i1})单元里,并且第 JJ 把钥匙是用来开启第 QiQ_i 类门的。(其中1QiP1\leq Q_i\leq P)。

输入数据中同一行各相邻整数之间用一个空格分隔。

输出格式

将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解,则输出 1-1

样例 #1

样例输入 #1

4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1

样例输出 #1

14

提示

Xi1Xi2+Yi1Yi2=1,0GiP|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1,0\leq G_i\leq P

1QiP1\leq Q_i\leq P

N,M,P10,K<150,S14N,M,P\leq10, K<150,S\leq 14