# 題目: UVa 10986 - Sending email

# 題目說明

有n台SMTP伺服器，以m條網路線互相連接
當一台SMTP伺服器向另一台SMTP伺服器傳送訊息時會產生延遲
求從s伺服器向v伺服器傳送訊息的最小延遲

---

INPUT:
第一行有一個整數T，代表有T筆測資
每筆測資第一行有四個整數n、m、s、t

1. n代表有n台SMTP伺服器
2. m代表有m條網路線
3. s代表起點
4. t代表終點

接下來有m行，每行有三個整數u、v、w
代表u伺服器向v伺服器傳送訊息會延遲w

---

OUTPUT:
輸出從s伺服器向v伺服器傳送訊息的最小延遲
如果訊息無法送達則輸出unreachable

# 解題方法

由於是無向圖，所以要建雙向的邊
以dijkstra演算法搭配priority_queue建出起點到每一個點的最小延遲
輸出終點的最小延遲

# 參考程式碼

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

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

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

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

	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, cases = 0;
	cin >> T;

	while (T--)
	{
		int n, m, s, t;
		cin >> n >> m >> s >> t;

		// init
		edge.assign(n, vector<p>());
		memset(vals, -1, sizeof(vals));
		memset(vis, false, sizeof(vis));

		// store data in both side
		while (m--)
		{
			int u, v, w;
			cin >> u >> v >> w;
			edge[u].push_back({ v, w });
			edge[v].push_back({ u, w });
		}

		// dijkstra algorithm
		dijkstra(s);

		cout << "Case #" << ++cases << ": ";
		if (vals[t] == -1) cout << "unreachable\n";
		else cout << vals[t] << "\n";
	}

	return 0;
}

# 參考資料

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