Poj Solution 1612

http://poj.org/problem?id=1612

#include<iostream>
using namespace std;

int dis[50][50],n;

void init()
{
    char c;
    int i,j,k;
    
    cin>>n;


    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            dis[i][j]=9999;
        dis[i][i]=0;
    }
    
    for(i=0;i<n;i++)
    {
        cin.get(c);
        while(cin.peek()!='n')
        {
            cin>>j;
            
            dis[i][j-1]=1;
            dis[j-1][i]=1;
        }
        
    }
    
    for(k=0;k<n;k++)
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    if(dis[i][k]<9999&&dis[k][j]<9999&&dis[i][k]+dis[k][j]<dis[i][j])
        dis[i][j]=dis[i][k]+dis[k][j];

}

void doit()
{
    int m,v[100],i,j,d,k;
    bool sign[100];
    char c;

    cin>>m;

    while(m--)
    {
        for(i=0;i<n;i++)
            sign[i]=0;
        
        i=0;
        if(cin.peek()=='n')
            cin.get(c);
        while(cin.peek()!='n')
        {
            cin>>v[i];
            if(cin.fail())break;
            v[i]--;
            
            if(v[i]<n&&sign[v[i]]==0)
            {
                sign[v[i]]=1;
                i++;
            }
            
        }
        d=i;



        for(i=0;i<n;i++)
        {
            for(j=0;j<d&&sign[i]==0;j++)
            for(k=0;k<d;k++)
                if(dis[v[j]][i]+dis[i][v[k]]==dis[v[j]][v[k]]&&dis[v[j]][v[k]]<9999)
                {
                    sign[i]=1;
                    break;
                }
        }

        for(i=0;i<n;i++)
            if(!sign[i])break;

        if(i>=n)cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    
}

int main()
{
    init();
    doit();
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *