Hố đen

#pragma warning (disable : 4996)
#include<iostream>

using namespace std;

#define maxQ 10000000


class Point {
public:
	int x, y;
	Point()
	{

	}

	Point(int a, int b)
	{
		x = a;
		y = b;
	}
};

class hoden {
public:
	Point A, B;
	int time;
};

class Queue {
	Point d[maxQ];
	int r, f;

public:
	Queue() {
		r = f = -1;
	}

	void reset()
	{
		r = f = -1;
	}

	void enQ(Point v)
	{
		r++;
		d[r].x = v.x;
		d[r].y = v.y;
	}

	Point deQ()
	{
		return d[++f];
	}

	bool isE()
	{
		return r == f;
	}
};

int T, N;
int map[1005][1005];
int Sx, Sy, Ex, Ey;
Point Start, End;
hoden hd[6];
int n, m;
int visited[1005][1005];
int checkhoden[1005][1005];

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
Queue q;

void init()
{
	q.reset();
	Start.x = Sx;
	Start.y = Sy;

	q.enQ(Start);

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			map[i][j] = visited[i][j] = 0;
			checkhoden[i][j] = -1;
		}
	}

	for (int i = 0; i < N; i++)
	{
		checkhoden[hd[i].A.x][hd[i].A.y] = checkhoden[hd[i].B.x][hd[i].B.y] = hd[i].time;
	}

	map[Sx][Sy] = 1;
}

Point find_way(Point a)
{
	for (int i = 0; i < N; i++)
	{
		if (a.x == hd[i].A.x && a.y == hd[i].A.y)
		{
			return hd[i].B;
		}
		else if(a.x == hd[i].B.x && a.y == hd[i].B.y)
		{
			return hd[i].A;
		}
	}
	return Point(-1,-1);
}

int bfs()
{
	init();

	while (!q.isE())
	{
		Point a = q.deQ();

		for (int i = 0; i < 4; i++)
		{
			int row = a.x + dx[i];
			int col = a.y + dy[i];

			if (row >= 0 && col >= 0 && row <= n && col <= n && map[row][col] == 0)
			{
				Point tmp(row, col);
				if (checkhoden[row][col] >= 0)
				{
					map[row][col] = map[a.x][a.y] + 1;
					Point new_way = find_way(tmp);
					map[new_way.x][new_way.y] = map[row][col] + checkhoden[row][col];
					q.enQ(new_way);
				}
				else
				{
					map[row][col] = map[a.x][a.y] + 1;
					q.enQ(tmp);
				}
			}
		}
	}
	return map[Ex][Ey];
}

int main()
{
	//freopen("input.txt", "r", stdin);
	cin >> T;
	for (int tc = 1; tc <= T; tc++)
	{
		cin >> N;
		cin >> Sx >> Sy >> Ex >> Ey;
		for (int i = 0; i < N; i++)
		{
			cin >> hd[i].A.x >> hd[i].A.y >> hd[i].B.x >> hd[i].B.y >> hd[i].time;
		}

		n = (Sx > Ex) ? Sx : Ex;
		m = (Sy > Ey) ? Sy : Ey;
		n = (n > m) ? n : m;
		m = n;
		cout << "#" << tc << " ";
		int kq = bfs();
		cout << kq - 1 << endl;
	}
	return 0;
}