TRAFFICN.cpp

#include <iostream>
using namespace std;

const int MAX_INT = 1000000000;
const int MAX = 10005;
const int MAX_QUEUE = 100000;

/*************Node biểu diễn một điểm***************/
typedef struct Node 
{
	int id, leng;
	Node *next;

	Node():id(0), leng(0){}
	Node(int _id, int _leng):id(_id), leng(_leng){}
}Node;
/**************************************************/

/**************Danh sách liên kết******************/
class List
{
public:
	Node *front;
public:
	List():front(0){}

	void Add(int id, int leng)
	{
		Node *tmp = new Node;

		tmp->id = id;
		tmp->leng = leng;
		tmp->next = front;

		front = tmp;
	}
};
/****************************************************/

int n, m, k, s, t, Answer;

bool Visit[2][MAX];
int  d[2][MAX];
//d[0] lưu khoảng cách ngắn nhất từ điểm s tới các điểm còn lại
//d[1] lưu khoảng cách ngắn nhất từ các điểm còn lại tới t

List Link[2][MAX];
//Link[0] lưu trạng thái đồ thị ban đầu
//Link[1] lưu trạng thái của đồ thị khi bị đảo ngược.

int leng;
Node Queue[MAX_QUEUE];

void Swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

/**********Triển khai hàng đợi ưu tiên dùng vun đống****************/
void Heapify(int leng, int i)
{
	int Left = 2*i + 1, Right = 2*i + 2;
	int Smallest;

	if (Left < leng && Queue[Left].leng < Queue[i].leng) Smallest = Left;
	else Smallest = i;

	if (Right < leng && Queue[Right].leng < Queue[Smallest].leng) Smallest = Right;
	
	if (Smallest != i)
	{
		Swap(Queue[i].leng,Queue[Smallest].leng);
		Swap(Queue[i].id,Queue[Smallest].id);
		Heapify(leng,Smallest);
	}
}

// Thêm phần tử vào cuối hàng đợi
void Enqueue(Node node)
{
	Queue[leng++] = node;
	
	if(leng >= 2)
	{
		int current = leng - 1;
		int parent  = (current - 1)/2;
		
		while (current > 0)
		{
			if(Queue[current].leng < Queue[parent].leng)
			{
				Swap(Queue[current].leng, Queue[parent].leng);
				Swap(Queue[current].id, Queue[parent].id);

				current = parent;
				parent = (current - 1)/2;
			}
			else break;
		}
	}
}

// Lấy ra phần tử ở đầu hàng đợi.
Node Dequeue()
{
	Node t = Queue[0];

	Queue[0].id = Queue[leng-1].id;
	Queue[0].leng = Queue[leng-1].leng;

	leng--;

	Heapify(leng,0);

	return t;
}
/******************************************************/

/*******Thuật toán Dijkstra tìm đường đi ngắn nhất*****/
void Dijkstra(int start, int type)
{
	d[type][start] = 0;

	leng = 0;
	Enqueue(Node(start,0));

	while(leng > 0)
	{
		Node node = Dequeue();

		if(Visit[type][node.id]) continue;
		Visit[type][node.id] = true;

		Node *p = Link[type][node.id].front;

		while(p != 0)
		{
			if(d[type][node.id] + p->leng < d[type][p->id])
			{
				d[type][p->id] = d[type][node.id] + p->leng;
				Enqueue(Node(p->id,d[type][p->id]));
			}

			p = p->next;
		}
	}
}
/*************************************************************/

int main()
{
	ios::sync_with_stdio(false);
//	freopen("input.txt","r",stdin);

	int T;
	cin >> T;

	for(int tc = 0; tc < T; tc++)
	{
		Answer = 0;
		cin >> n >> m >> k >> s >> t;
		
		for(int i = 0; i <= n; i++)
		{
			for(int k = 0; k < 2; k++)
			{
				Link[k][i].front = 0;
				Visit[k][i] = false;
				d[k][i] = MAX_INT;
			}
		}

		int a, b, c;

		for(int i = 0; i < m; i++)
		{
			cin >> a >> b >> c;

			Link[0][a].Add(b,c);
			Link[1][b].Add(a,c);
		}

		// Tìm đường đi ngắn nhất từ s tới các điểm còn lại
		Dijkstra(s,0);
		Answer = d[0][t];

		// Tìm đường đi ngắn nhất từ mọi điểm đến điểm t
		Dijkstra(t,1);

		// Tìm đường đi ngắn nhất
		for(int i = 0; i < k; i++)
		{
			cin >> a >> b >> c;

			if(d[0][a] + c + d[1][b] < Answer) Answer = d[0][a] + c + d[1][b];
			if(d[0][b] + c + d[1][a] < Answer) Answer = d[0][b] + c + d[1][a];
		}

		if(Answer == MAX_INT) Answer = -1;

		cout << Answer << endl;
	}

	return 0;
}