範例程式碼 uva11792
//uva11792
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int t;
cin >> t;
int n, m;
vector<int> g[10005];
int path[10005];
while (t--) {
cin >> n >> m;
for (int i = 0; i <= n; ++i) {
g[i].clear();
path[i] = 0;
}
int pre, next;
for (int i = 0; i < m; ++i) {
cin >> pre;
++path[pre];
while (cin >> next) {
if (!next)
break;
g[pre].push_back(next);
g[next].push_back(pre);
pre = next;
++path[pre];
}
}
int res = -1, mn = 1999999999;
int dist[10005];
int used[10005];
int tmp = 0;
queue<int> Q;
for (int i = 1; i <= n; ++i) {
if (path[i] > 1) {
Q = queue<int>();
for (int j = 0; j <= n; ++j) {
dist[j] = 1999999999;
used[j] = 0;
}
dist[i] = 0;
Q.push(i);
int tn;
while (!Q.empty()) {
tn = Q.front();
Q.pop();
used[tn] = 0;
for (int j = 0; j < g[tn].size(); ++j) {
if (dist[g[tn][j]] > dist[tn] + 1) {
dist[g[tn][j]] = dist[tn] + 1;
if (!used[g[tn][j]]) {
used[g[tn][j]] = 1;
Q.push(g[tn][j]);
}
}
}
}
tmp = 0;
for (int j = 1; j <= n; ++j) {
if (path[j] > 1)
tmp += dist[j];
}
if (tmp < mn) {
mn = tmp;
res = i;
}
}
}
cout << "Krochanska is in: " << res << endl;
}
}