Uva 10044 Solution

#include<bits/stdc++.h>

#define L 100000

#define pii pair<string, int>

using namespace std;

vector<int>v[L];

int vis[L], dis[L];

set<int>ss;

void clear1()

{

for(int i=0;i<L;i++)

{

v[i].clear();

vis[i] = dis[i] = 0;

}

}

void bfs()

{

vis[0] = 1;

dis[0] = 0;

queue<int>q;

q.push(0);

while(!q.empty())

{

int x = q.front();

q.pop();

ss.insert(x);

for(auto p : v[x])

{

if(vis[p] == 0)

{

vis[p] = 1;

dis[p] = dis[x] + 1;

q.push(p);

}

}

}

}

int main()

{

int t, n, m, k = 1;

cin >> t;

while(t--)

{

cin >> n >> m;

map<string, int>mp;

int c = 0;

mp["Erdos, P."] = 0;

getchar();

while(n--)

{

string st;

getline(cin, st);

string pc = "";

vector<string>s;

for(int i=0;i<st.size();i++)

{

if(st[i] == ',' && st[i-1] == '.')

{

s.push_back(pc);

i++;

pc = "";

}

else if(st[i] == ':' && st[i-1] == '.')

{

s.push_back(pc);

break;

}

else

pc = pc + st[i];

}

for(int i=0;i<s.size();i++)

{

if(s[i] != "Erdos, P." && mp[s[i]] == 0)

{

c++;

mp[s[i]] = c;

}

}

for(int i=0;i<(s.size()-1);i++)

{

int id1 = mp[s[i]];

for(int j=i+1;j<s.size();j++)

{

int id2 = mp[s[j]];

v[id1].push_back(id2);

v[id2].push_back(id1);

}

}

}

bfs();

string st;

vector<pii>v3;

while(m--)

{

getline(cin, st);

int id1 = mp[st];

if(ss.find(id1) == ss.end())

v3.push_back({st, 0});

else

v3.push_back({st, dis[id1]});

}

cout << "Scenario " << k++ << "\n";

for(int i=0;i<v3.size();i++)

{

if(v3[i].second == 0)

cout << v3[i].first << " " << "infinity" << "\n";

else

cout << v3[i].first << " " << v3[i].second << "\n";

}

clear1();

ss.clear();

}

return 0;

}