小Y被关在了一个N*M(M, N<=15)的迷宫中，迷宫里有不可逾越的墙和P种门(p<=10)。从一个格 子移动到另一个格子的时间是1，有些格子里有P种门的钥匙，拿所在格子钥匙的时间以及用钥匙开 门的时间不计。 作为一个朋友，你的任务是用最少的时间救出小Y。 小Y在第N行第M列的位置，刚开始你在第一行第一列的位置。

第1行3个整数，表示N，M，P的值，之间有一个空格分开。 第2行1个整数K，表示迷宫中门和墙的总个数。 以后K行，每行5个数，分别为X1,Y1,X2,Y2和G，之间有一个空格分开。 G>0时，代表(X1,Y1)->(X2,Y2)有一个G类的门。 G=0时，代表(X1,Y1)->(X2,Y2)有一个墙，其中|X1-X2|+|Y1-Y2|=1。 然后1行是一个整数S，代表了钥匙的个数。 然后S行，每行3个数X,Y,Q，之间有一个空格分开，代表(X,Y)位置有一个开启Q门的钥匙。

输出一行一个整数，代表救出小Y的最少时间，若不能救出，则输出“Poor”,不包括引号。

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

14

2011年复赛培训题