# 題目: UVa 11792 - Krochanska is Here

# 題目說明

給m條路線，其中有重複的車站稱為重點車站，求哪一個重點車站到其他所有重點車站的距離最短
(題目中文翻譯可參考: 天然呆 翻譯 UVa 11792 Krochanska is Here!)

---

INPUT:
第一行輸入一個整數t，代表測資數
每筆測資先輸入兩個整數n、m，n為車站數、m為路線數
接下來有m行，每行輸入數個整數，代表此路線的車站，以0當作結尾

---

OUTPUT:
輸出哪一個重點車站到其他所有重點車站的距離最短

# 解題方法

先建表，由於車站到車站是雙向的，屬於無向圖，所以需要建雙邊
使用cross紀錄車站是否為重點車站
對每個重點車站跑dijkstra演算法，找尋此重點車站到其他每個重點車站的距離
因為所有車站到車站的距離都視為相同，所以不需要紀錄weight，dijkstra使用普通的queue即可，不需要使用priority queue
最後再比對哪個重點車站到其他所有重點車站的距離最短

# 參考程式碼

#include <iostream>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

static auto fast_io = []
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	return 0;
}();

vector< vector<int> > G;
vector<int> cross;

int dijkstra(int root, int n)
{
	vector<int> dist(n + 1, INT_MAX);
	vector<bool> vis(n + 1, false);
	queue<int> Q;
	int cnt = 0;

	dist[root] = 0;
	Q.push(root);
	
	while (!Q.empty())
	{
		int u = Q.front(); Q.pop();

		for (auto& i : G[u])
		{
			if (dist[i] > dist[u] + 1)
			{
				dist[i] = dist[u] + 1;
				if (!vis[i]) vis[i] = true, Q.push(i);
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		if (cross[i] <= 1) continue;
		cnt += dist[i];
	}

	return cnt;
}

int main()
{
	int t, n, m;
	cin >> t;

	while (t--)
	{
		cin >> n >> m;

		int v, u;
		int Min = INT_MAX, ret = 0;
		G.assign(n + 1, vector<int>());
		cross.assign(n + 1, 0);

		while (m--)
		{
			cin >> v;
			++cross[v];
			while (cin >> u, u)
			{
				G[v].push_back(u);
				G[u].push_back(v);
				++cross[u];
				v = u;
			}
		}

		for (int i = 1; i <= n; ++i)
		{
			if (cross[i] <= 1) continue;

			int cnt = dijkstra(i, n);
			if (cnt < Min) ret = i, Min = cnt;
		}

		cout << "Krochanska is in: " << ret << "\n";
	}
}

# 參考資料

https://m80126colin.github.io/blog/articles/%E7%BF%BB%E8%AD%AF/uva/uva11792/
https://theriseofdavid.github.io/2021/09/14/UVa/UVa11792/