BZOJ 3417 Poi2013 Tales of seafaring BFS

题目大意：给定一张无向图，每条边边权都是1，多次询问是否存在某个点到达另一个点的长度为d的路径

首先如果s和t是同一点且这个点没有出边 那么s到t只存在长度为0的路径

否则：

如果s到t有长度为d的路径 那么就一定有长度为d+2的路径

因此只要BFS求出s开始到每个点的奇数长度的最短路和偶数长度的最短路就行了

为了防止爆内存可以预先将询问离线化

时间复杂度O(n(n+m))

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 5050
using namespace std;
struct Query{
	int s,t,d;
	Query() {}
	Query(int _,int __,int ___):
		s(_),t(__),d(___) {}
}queries[1001001],*q[1001001];
struct abcd{
	int to,next;
}table[M<<1];
int head[M],tot;
int n,m,k;
int f[M][2];
bool ans[1001001];
void Add(int x,int y)
{
	table[++tot].to=y;
	table[tot].next=head[x];
	head[x]=tot;
}
bool Compare(Query *x,Query *y)
{
	return x->s < y->s;
}
void BFS(int x)
{
	static pair<int,bool> q[M<<1];
	int i,r=0,h=0;
	memset(f,0x3f,sizeof f);
	f[x][0]=0;
	q[++r]=make_pair(x,0);
	while(r!=h)
	{
		pair<int,bool> temp=q[++h];
		int x=temp.first;
		bool flag=temp.second;
		for(i=head[x];i;i=table[i].next)
			if(f[table[i].to][!flag]==0x3f3f3f3f)
				f[table[i].to][!flag]=f[x][flag]+1,q[++r]=make_pair(table[i].to,!flag);
	}
}
int main()
{
	int i,j,x,y,d;
	cin>>n>>m>>k;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		Add(x,y);Add(y,x);
	}
	for(i=1;i<=k;i++)
	{
		scanf("%d%d%d",&x,&y,&d);
		q[i]=new (&queries[i])Query(x,y,d);
	}
	sort(q+1,q+k+1,Compare);
	for(j=1,i=1;i<=n;i++)
	{
		BFS(i);
		for(;j<=k&&q[j]->s==i;j++)
		{
			x=q[j]->s;
			y=q[j]->t;
			d=q[j]->d;
			if( x==y && !head[x] )
				ans[q[j]-queries]=!d;
			else
				ans[q[j]-queries]=f[y][d&1]<=d;
		}
	}
	for(i=1;i<=k;i++)
		puts(ans[i]?"TAK":"NIE");
	return 0;
}

BZOJ 3417 Poi2013 Tales of seafaring BFS

原文：http://blog.csdn.net/popoqqq/article/details/44590185