Thursday, 18 February 2016

UVa 567 - Risk

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int cas=1,nn;
    while(cin>>nn)
    {
        vector<int>nodes[1000];
        int i,j,k,l,m,n,a,b;
        for(i=0;i<nn;i++)
        {
            cin>>a;
            b=1;
            nodes[b].push_back(a);
            nodes[a].push_back(b);
        }
        for(i=1;i<19;i++)
        {
            cin>>nn;
            b=i+1;
            for(j=0;j<nn;j++)
            {
                cin>>a;
                nodes[a].push_back(b);
                nodes[b].push_back(a);
            }
        }
        int node1,node2;
        cin>>m;
        {
            cout<<"Test Set #"<<cas<<endl;
            cas++;
            for(i=0;i<m;i++)
            {
                cin>>node1>>node2;
                queue<int>q;
                bool visited[1000];
                memset(visited,0,sizeof(visited));
                int level[1000];
                //memset(visited,0,sizeof(visited));
                int ans,node;
                visited[node1]=true;
                level[node1]=0;
                q.push(node1);
                while(!q.empty())
                {
                    int f=q.front();
                    for(j=0;j<nodes[f].size();j++)
                    {
                        int v=nodes[f][j];
                        if(visited[v]==false)
                        {
                            level[v]=level[f]+1;
                            visited[v]=true;
                            q.push(v);
                        }
                        if(v==node2)
                        {
                            //cout<<55555555<<endl;
                            ans=level[v];
                        }
                    }
                    q.pop();
                }
                printf("%2d to %2d: %d\n",node1,node2,ans);
            }

        }
        cout<<endl;
    }
    return 0;
}

No comments:

Post a Comment