Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Posted by teitoku at 2018-03-23 15:22:13 on Problem 2457
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator