範例程式碼 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;
  }
}