2013年3月11日

UVa 10044 - Erdos Numbers


#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;

void BFS(map<string, int>& d, vector<vector<string> >& v) {
  int i, j, k;
  map<string, set<string> > con;
  for (i = 0; i < v.size(); i++)
    for (j = 0; j < v[i].size(); j++)
      for (k = j + 1; k < v[i].size(); k++) {
        con[v[i][j]].insert(v[i][k]);
        con[v[i][k]].insert(v[i][j]);
      }
  queue<string> q;
  q.push("Erdos,P.");
  d["Erdos,P."] = 0;
  bool find = 0;
  while (!q.empty()) {
    string now = q.front();
    q.pop();
    int dis = d[now];
    for (set<string>::iterator it = con[now].begin(); it != con[now].end(); it++)
      if (!d.count(*it)) {
        q.push(*it);
        d[*it] = dis + 1;
      }
  }
}

int main() {
  int T, C = 1;
  scanf("%d\n", &T);
  while (T--) {
    int p, n, i, j, k;
    scanf("%d %d\n", &p, &n);
    vector<vector<string> > v;
    string s, name;
    while (p--) {
      getline(cin, s);
      for (i = 0; s[i]; i++)
        if (s[i] == ' ') s.erase(s.begin() + i--);
      vector<string> vs;
      for (i = 0, j = 0; ; i++) {
        if (s[i] == ',' || s[i] == ':') {
          j++;
          if (j == 2) {
            vs.push_back(name);
            j = 0;
            name.clear();
            if (s[i] == ':') break;
            continue;
          }
        }
        name.insert(name.end(), s[i]);
      }
      v.push_back(vs);
    }
    map<string, int> d;
    BFS(d, v);
    printf("Scenario %d\n", C++);
    while (n--) {
      getline(cin, s);
      name = s;
      for (i = 0; s[i]; i++)
        if (s[i] == ' ') s.erase(s.begin() + i--);
      if (d.count(s)) printf("%s %d\n", name.c_str(), d[s]);
      else printf("%s infinity\n", name.c_str());
    }
  }
  return 0;
}

沒有留言:

張貼留言