2013年8月17日

UVa 11792 - Krochanska is Here!

#include <cstdio>
#include <vector>
#include <queue>
#define MP make_pair
#define PB push_back
using namespace std;

typedef pair<int, int> P;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N, S;
    scanf("%d%d", &N, &S);
    int times[10001] = {};
    vector<int> con[10001];
    while (S--) {
      int pre, now;
      scanf("%d", &pre);
      if (!pre) {
        continue;
      }
      times[pre]++;
      while (scanf("%d", &now) && now) {
        times[now]++;
        con[pre].PB(now);
        con[now].PB(pre);
        pre = now;
      }
    }
    vector<int> important;
    for (int i = 1; i <= N; i++) {
      if (times[i] > 1) {
        important.PB(i);
      }
    }
    int min = 2e9, ans = 0;
    for (int i = 0; i < important.size(); i++) {
      int start = important[i];
      bool vis[10001] = {};
      vis[start] = true;
      queue<P> q;
      q.push(MP(start, 0));
      int sum = 0, found = 0;
      while (!q.empty()) {
        int now = q.front().first, dis = q.front().second;
        q.pop();
        if (times[now] > 1) {
          found++;
          sum += dis;
          if (found == important.size()) {
            break;
          }
        }
        for (int j = 0; j < con[now].size(); j++) {
          if (!vis[con[now][j]]) {
            vis[con[now][j]] = true;
            q.push(MP(con[now][j], dis + 1));
          }
        }
      }
      if (sum < min) {
        min = sum;
        ans = start;
      }
    }
    printf("Krochanska is in: %d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言