Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

NOIP2014 TG T5 寻找道路

Jacinth posted @ 2015年8月16日 16:16 in NOIP with tags NOIP Learning , 545 阅读

感觉自己弱爆了是吧,还在做去年的NOIP的T5,真心不知道当年用的是什么傻B算法反正那时就10分,完全代表窝Day2报废了对吧

然后终于A了

感觉自己拖延症真心讨厌啊。。。

拖了这么久才来A这道出了考场问了大神就知道算法的题

两遍BFS不用说,当时不会邻接表,现在终于会了。。。(表示不怎么理解,就是把代码背了,求大神教导%%%)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <string>
#include <algorithm>
#define NN 10100
#define MM 200100
using namespace std;

queue <int> que;
queue <int> dis;

int ne1[MM],ne2[MM],head1[MM],head2[MM],v1[MM],v2[MM];
int tota,totb;
int x,y,s,t,n,m;
bool f[NN],used[NN];

void Build(int xx,int yy)
{
	ne1[++tota]=head1[xx]; head1[xx]=tota; v1[tota]=yy;
	ne2[++totb]=head2[yy]; head2[yy]=totb; v2[totb]=xx; 
}

void BFSa()
{
	while (!que.empty()) que.pop();
	que.push(t);
	f[t] = 0;
	while (!que.empty())
	{
		int h=que.front(); que.pop();
		for (int i=head2[h];i;i=ne2[i])
		{
			if (f[v2[i]])
			{
				f[v2[i]]=0;
				que.push(v2[i]);
			}
		}
	}
	return;
}

bool check(int xx)
{
	for (int i=head1[xx];i;i=ne1[i])
		if (f[v1[i]]) return 0;
	return 1;
}

void BFSb()
{
	while (!que.empty()) que.pop();
	while (!dis.empty()) dis.pop();
	que.push(s);
	dis.push(0);
	used[s]=1;
	while (!que.empty())
	{
		int h=que.front(); que.pop();
		int d=dis.front(); dis.pop();
		if (!check(h)) continue;
		for (int i=head1[h];i;i=ne1[i])
		{
			if (!used[v1[i]])
			{
				if (v1[i]==t)
				{
					printf("%d\n",d+1);
					return;
				}
				que.push(v1[i]);
				used[v1[i]]=1;
				dis.push(d+1);
			}
		}
	}
	puts("-1");
	return;
}

int main()
{
	scanf("%d%d",&n,&m);
	tota=totb=0;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		if (x!=y)  Build(x,y);
	}
	scanf("%d%d",&s,&t);
	memset(f,1,sizeof(f));
	BFSa();
	memset(used,0,sizeof(used));
	if (f[s]) 	{ puts("-1"); return 0; }
	BFSb();
	return 0;
}

不管怎么样,A题总是一件欢乐的事对吧~~


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter