# 題目: UVa 1112 - Mice and Maze

# 題目說明

有一張有向圖，每個點走到另一個點都會花費時間
每個點走到終點都有一條最短路徑
求有多少點能在時間限制內走到終點

---

INPUT:
第一行有一個整數T，代表有T筆測資
每筆測資第一行有四個整數N、End、Time、M

1. N代表有N個點
2. End代表終點
3. Time代表時間限制
4. M代表有幾個邊

接下來有M行，每行有三個整數u、v、w
代表u點及v點間有一條長w的邊

---

OUTPUT:
輸出能在時間限制內走到終點的點的數量

# 解題方法

如果從每個點開始走到終點，會很麻煩，所以改為從終點開始走(存edge的時候反向存)
以dijkstra演算法搭配priority_queue建出終點到每一個點的最小路徑
最後再判斷每個點的最小路徑有沒有在時間限制內

# 參考程式碼

#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>

using namespace std;
typedef pair<int, int> p;

vector< vector<p> > edge;
priority_queue<p, vector<p>, greater<p>> pq;
int vals[101];
int vis[101];

void dijkstra(int End)
{
	vals[End] = 0;
	pq.push({ 0, End });

	while (!pq.empty())
	{
		auto [val, u] = pq.top();
		pq.pop();
		vis[u] = true;
		
		for (auto& [v, w] : edge[u]) if (!vis[v])
		{			
			int tmp = val + w;
			if (vals[v] == -1 || vals[v] > tmp)
			{
				vals[v] = tmp;
				pq.push({ tmp, v });
			}
		}
	}
}

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;

	while (T--)
	{
		int N, End, Time, M;
		cin >> N >> End >> Time >> M;

		// init
		edge.assign(N + 1, vector<p>());
		memset(vis, false, sizeof(vis));
		for (int i = 0; i < 101; ++i) vals[i] = Time + 1;

		while (M--)
		{
			int u, v, w;
			cin >> u >> v >> w;
			edge[v].push_back({ u, w });
		}

		// dijkstra algorithm
		dijkstra(End);

		int count = 0;
		for (int i = 1; i <= N; ++i) if (vals[i] <= Time) ++count;

		cout << count << "\n";
		if (T) cout << "\n";
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%201112/