Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
水#include<stdio.h> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<iostream> using namespace std; const int inf=1<<30; const int maxn=50100; int cost[maxn]; vector<int>v[maxn]; int pre[maxn]; int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { fill(cost,cost+maxn,inf); for(int i=0;i<maxn;i++) v[i].clear(); for(int i=0;i<maxn;i++) pre[i]=i; for(int i=1;i<=n;i++) { int p,q; scanf("%d%d",&p,&q); v[p].push_back(q); } queue<int>q; q.push(1); cost[1]=1; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=0;i<v[now].size();i++) { if(cost[v[now][i]]>cost[now]+1) { cost[v[now][i]]=cost[now]+1; pre[v[now][i]]=now; q.push(v[now][i]); } } } if(cost[k]==inf) { puts("-1"); } else { int now=k; stack<int>st; while(now!=1) { st.push(now); now=pre[now]; } printf("%d\n1\n",cost[k]); while(!st.empty()) { printf("%d\n",st.top()); st.pop(); } } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator