Poj Solution 2781

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

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


#define INF 3000000
#define NMAX 1000000
int N;
typedef struct 
{
    int len;
    int next[101];
}DATA;
DATA a[NMAX];
int st,ed;
void input()
{
    int i,j;
    scanf("%d",&N);
    int tmp;
    for(i=0;i<N;i++)
    {
        scanf("%d%d",&tmp,&a[i].len);
        for(j=0;j<a[i].len;j++)
        {
            scanf("%d",&a[i].next[j]);
        }
        a[i].next[j]=-1;
    }
    scanf("%d%d",&st,&ed);
}
int m[NMAX]={0};
int p,q;
int que[NMAX];

void solve()
{
    int i;
    for(i=0;i<N;i++)
        m[i]=INF;
    que[0]=st;
    p=0;
    q=1;
    m[st]=0;
    int cp;
    while(p<q)
    {
        cp=que[p++];
        for(i=0;i<a[cp].len;i++)
        {
            if(m[a[cp].next[i]]>m[cp]+1)
            {
                m[a[cp].next[i]]=m[cp]+1;
                que[q++]=a[cp].next[i];
            }
        }

    }
    printf("%d %d %d",st,ed,m[ed]-1);
    
}
int main()
{

#if _DEBUG    
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

#endif
    input();
    solve();
    
        
#if _DEBUG
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

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