SPOJ.COM - Thuật toán bài TRAFFICN - Traffic Network

Posted on October 23rd, 2016

Đề bài:

Mạng lưới giao thông thành phố gồm n nút được đánh số từ 1 đến n và m đường một chiều nối các cặp nút. Để giảm được độ dài của đường đi ngắn nhất giữa hai nút trọng yếu s và t khác nhau, một danh sách gồm k đường hai chiều được đề xuất để xem xét xây dựng.

Nhiệm vụ của bạn là viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất giữa s và t là nhỏ nhất.

Đầu vào

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa năm số nguyên dương n (n ≤ 10 000), m (m ≤ 100 000), k (k < 300), s (1 ≤ s ≤ n), t (1 ≤ t ≤ n) cách nhau bởi dấu trống.

Dòng thứ i trong m dòng tiếp theo chứa ba số nguyên dương di, ci, li cách nhau bởi dấu trống, trong đó li là độ dài ( 0< li ≤ 1000) của đường một chiều thứ i từ nút di đến nút ci.

Dòng thứ j trong k dòng tiếp theo chứa ba số nguyên dương uj, vj và qj (qj ≤ 1000) cách nhau bởi dấu trống, trong đó qj là độ dài của đường hai chiều được đề xuất thứ j nối giữa hai nút uj và vj.

Đầu ra

Với mỗi bộ dữ liệu, ghi ra trên một dòng độ dài nhỏ nhất có thể của đường đi ngắn nhất giữa hai nút trọng yếu sau khi xây dựng xong một đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ s đến t, ghi -1.

Ví dụ

Đầu vào:

1 
4 5 3 1 4 
1 2 13
2 3 19 
3 1 25 
3 4 17 
4 1 18 
1 3 23 
2 3 5 
2 4 25 

Đầu ra:

35 

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/TRAFFICN/en/

Phân tích

Trong bài toán này mình sẽ sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ điểm s tới tất cả các điểm còn lại và tìm đường đi ngắn nhất từ tất cả các điểm còn lại đến điểm t.

Sau đó mình sẽ duyệt các con đường trong k con đường dự kiến cần thay thế. Giả sử 1 con đường từ a đến b và khoảng cách của nó là c. Khi đó, đường đi ngắn nhất của a và b sẽ bằng: Min{kc(s, a) + c + kc(b, t), kc(s, b) + c + kc(a, t)}

Trong đó:

  • kc(s, a) là khoảng cách đường đi ngắn nhất từ s tới a (tương tự với b)
  • kc(b, t) là khoảng cách đường đi ngắn nhất từ b tới t (tương tự với a).

Sau khi duyệt hết k con đường ta sẽ tìm được giá trị cần tính.

Chú ý:

  • ở đây, do số lượng điểm và số con đường rất lớn nên ta không thể dùng ma trận kề được. Ở đây, mình dùng danh sách liên kết.
  • Đối với thuật toán Dijkstra, nếu muốn sử dụng thư viện, bạn có thể sử dụng thư viện hàng đợi ưu tiên (trong c++ hàng đợi ưu tiên là priority_queue nằm trong thư viện <queue>). Ở đây, mình sẽ triển khai (implement) lại hàng đợi ưu tiên sử dụng kỹ thuật vun đống. Nếu bạn sử dụng cách khác thì khả năng time limit là vô cùng cao.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#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;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé: