zzuli 2130: hipercijevi bfs + 입 출력 외 장 (2017 경공업 학교 경기)

2130: hipercijevi
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 749 Solved: 156
SubmitStatusWeb Board Description
먼 은하계 에서 가장 빠 른 교통 방식 은 어떤 파 이 프 를 사용 하 는 것 이다.파이프 마다 N 개의 역 을 직접 연결 합 니 다.그러면 우 리 는 첫 번 째 역 에서 N 번 째 역 까지 최소 몇 개의 역 을 지나 야 합 니까?
Input
파일 을 입력 하 는 첫 번 째 행동 T 는 T 그룹 데이터 가 있 음 을 표시 합 니 다.
각 데이터 의 첫 줄 에는 세 개의 정수 N (1 < = N < = 100000) 이 역 의 개 수 를 나타 내 는 것 을 포함한다.K (1 & lt; = K & gt; = 1000) 는 하나의 파이프 가 몇 개의 역 에 직접 연결 되 었 는 지 나타 낸다.M (1 & lt; = M & gt; = 1000) 은 파이프 의 수량 을 나타 낸다.
다음 M 줄 은 각 줄 에 하나의 파이프 에 대한 설명 을 포함 합 니 다. K 개의 정수 로 이 파이프 가 연 결 된 K 개의 역 번 호 를 표시 합 니 다.
Output
출력 파일 T 줄 은 첫 번 째 역 에서 N 번 째 역 까지 최소 몇 개의 역 을 거 쳐 야 하 는 지 를 나타 내 는 정수 가 포함 되 어 있 습 니 다.첫 번 째 역 에서 N 번 째 역 에 도착 하지 못 하면 출력 - 1.
Sample Input
2 9 3 5 1 2 3 1 4 5 3 6 7 5 6 7 6 8 9 15 8 4 11 12 8 14 13 6 10 7 1 5 8 12 13 6 2 4 10 15 4 5 9 8 14 12 11 12 14 3 5 6 1 13
Sample Output
43 나 는 모든 파 이 프 를 하나의 점 으로 생각 했 지만, vector 를 사용 하 는 것 은 시간 을 초과 했다.그 때 는 잘못 생각 한 줄 알 고 계속 하지 않 았 습 니 다.드디어 A 야.

#include 
#include 
#include 
using namespace std;
struct node
{
    int next;
    int to;
}edge[1005*1005*2];
int pit[100000+1005];
int dist[100000+1005];
int time;
//     
inline void scan_d(int &ret) 
{
    char c; 
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    { 
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}
//        
void out(int a) 
{  
    if (a < 0) 
    {
        putchar('-');
        a = -a;
    }  
    if (a >= 10)
    {
       out(a / 10);  
    }
    putchar(a % 10 + '0');  
}  
void addedge(int x,int y)
{
    edge[time].next=pit[x];
    edge[time].to=y;
    pit[x]=time++;
}
int bfs(int S,int T)
{
    queue<int>s;
    int s1,u,to;
    s.push(S);
    while(!s.empty())
    {
        s1=s.front();s.pop();
        for(u=pit[s1];u!=-1;u=edge[u].next)
        {
            to=edge[u].to;
            if(!dist[to])
            {
                dist[to]=dist[s1]+1;    
                s.push(to);
                if(to==T) return dist[T]/2+1;
            }
        }
    }
    return -1;
}
int main()
{
    int ncase;
    scan_d(ncase);
    while(ncase--)
    {
        int n,k,m,x;
        time=0;
        scan_d(n);scan_d(k);scan_d(m);
        memset(pit,-1,sizeof(int)*(n+m+10));
        memset(dist,0,sizeof(int)*(n+m+10));
        for(int i=0;ifor(int j=0;j1);
                addedge(n+i+1,x);
            }
        }
        out(bfs(1,n));
        putchar('
');
    }
    return 0;
}