SPOJ.COM - Thuật toán bài MICEMAZE - Mice and Maze

Đề bài:

Một tập hợp những con chuột thí nghiệm đang được huấn luyện để thoát khỏi mê cung. Mê cung được tạo bởi những ô, mà mỗi ô được kết nối tới những ô khác. Tuy nhiên, sẽ có những vật cản trên đường đi giữa các ô. Vì vậy, sẽ cần thêm thời gian để vượt qua những vật cản này. Một vài đường chỉ cho phép con chuột đi theo một chiều và không có đường vòng.

Giả sử là tất cả lũ chuột đã được huấn luyện, khi được đặt ở một ô bất kì trên mê cung, tìm đường để đưa chúng ra khỏi mê cung với thời gian ngắn nhất.

Chúng ta sẽ làm một thí nghiệm như sau: mỗi một con chuột được đặt vào một ô trên mê cung và một đồng hồ đếm ngược được bắt đầu. Khi đồng hồ dừng lại, đếm số chuột thoát ra được mê cung.

Vấn đề:

Viết một chương trình, cho trước thông tin của những con chuột và thời gian giới hạn. Dự đoán số chuột thoát ra được khỏi mê cung. Giả sử rằng sẽ không có nút thắt cổ chai nào trên mê cung, tất cả các ô sẽ có đủ khoảng trống để chứa số lượng chuột ngẫu nhiên.

Đầu vào

Các ô trong mê cung được đánh số từ 1 đến N, trong đó N là số lượng ô, N <= 100. Ba dòng đầu tiên chứa số N - số lượng ô, E - chỉ số của ô lối thoát và giá trị T là thời gian bắt đầu của đồng hồ đếm ngược.

Dòng thứ 4 là số M - số lượng kết nối trong mê cung. Sau đó là M dòng. Mỗi dòng xác định 1 kết nối, bao gồm 3 số là số a, b và c. Trong đó a, b là chỉ số của các ô (a, b thuộc từ 1 đến N), và c là thời gian cần để đi từ a đến b.

Chú ý rằng mỗi kết nối là một chiều, tức là con chuột không thể đi từ b về a trừ khi có kết nối từ b đến a. Cũng chú ý là, thời gian di chuyển trên mỗi hướng là khác nhau.

Đầu ra

Mỗi test case in ra trên một dòng, là số lượng chuột đến được ô thoát Exit của mê cung trong thời gian T.

Ví dụ

Đầu vào:

4 
2 
1
8
1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 2 1
4 3 1

Đầu ra:

3

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

Phân tích

Theo suy luận thông thường, mình sẽ phải xét mỗi con chuột, tìm đường đi ngắn nhất của nó đến ô thoát. Kiểm tra xem thời gian đó có nhỏ hơn hoặc bằng thời gian giới hạn T hay không. Nếu thỏa mãn thì con chuột đó sẽ thoát được khỏi mê cung trong thời gian cho phép. Tuy nhiên, nếu xét riêng từng con như vậy, chắc chắn sẽ bị time limit.

Bài toán ở đây là tìm đường đi ngắn nhất từ N điểm đến 1 điểm. Thực chất, mình sẽ quy về bài toán tìm đường đi ngắn nhất từ 1 điểm đến N điểm. Bằng cách đảo ngược lại chiều của các đường đi.

Để tìm đường đi ngắn nhất từ một điểm đến N điểm, mình sử dụng thuật toán Dijkstra

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 = 1 << 20;
const int MAX = 105;

int N, M, E, T;
int Matrix[MAX][MAX];
int Mark[MAX], Value[MAX];

int FindIdMinValue()
{
	int idm = 0, _min = MAX_INT;
	for(int i = 1; i <= N; i++)
		if(Mark[i] == 0 && Value[i] < _min)
		{
			_min = Value[i];
			idm  = i;
		}
	return idm;
}

void Dijkstra(int start)
{
	int cnt = 0;
	for(int i = 1; i <= N; i++)
	{
		Mark[i] = 0;
		Value[i] = MAX_INT;
	}

	Value[start] = 0;
	while(cnt < N)
	{
		int idmin = FindIdMinValue();
		Mark[idmin] = 1;
		cnt++;
		for(int i = 1; i <= N; i++)
			if(Mark[i] == 0 && Matrix[idmin][i] > 0 &&
				Value[idmin] + Matrix[idmin][i] < Value[i])
				Value[i] = Value[idmin] + Matrix[idmin][i];
	}
}

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

	cin >> N >> E >> T >> M;
	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= N; j++)
			Matrix[i][j] = 0;

	int a, b, t;
	for(int i = 0; i < M; i++)
	{
		cin >> a >> b >> t;
		Matrix[b][a] = t;
	}

	// implementing code
	Dijkstra(E);

	// Đếm những ô có giá trị <= T
	// là những ô con chuột có thể thoát.
	int Answer = 0;
	for(int i = 1; i <= N; i++)
		if(Value[i] <= T) Answer++;

	// output
	cout << Answer << endl;
	return 0;
}