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

我BFS WA了,别人DFS 过了,想不通一点

Posted by stupidjohn at 2010-08-22 09:06:19 on Problem 1394
#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,int> tmap;
struct node
{
	int start,end,des;
	int next;
}mymalloc[10000];
int my;
int bedtime,n,m,s,t;
int city[101];
string from,to;
bool init()
{
	int i,j,k,l,f;
	string ss[101];
	int sche[101];
	scanf("%d",&n);
	if(!n) return false;
	tmap.clear();
	my=0;
	memset(city,-1,sizeof(city));
	for(i=0;i<n;i++)
	{
		cin>>ss[0];
		tmap[ss[0]]=i;
	}
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{
		scanf("%d",&k);
		for(j=0;j<k;j++)
		{
			cin>>sche[j];
			cin>>ss[j];
		}
		for(j=0;j<k-1;j++)
		{
			l=j+1;
			mymalloc[my].start=sche[j];
			mymalloc[my].end=sche[l];
			mymalloc[my].des=tmap[ss[l]];
			f=tmap[ss[j]];
			mymalloc[my].next=city[f];
			city[f]=my;
			my++;
		}
	}
	scanf("%d",&bedtime);
	cin>>ss[0]>>ss[1];
	from=ss[0];to=ss[1];
	s=tmap[ss[0]];t=tmap[ss[1]];
	return true;
}
bool check[101];
int currentstart,cnt;
int bestend,beststart;
bool search(int pos,int nowtime)
{
//	if(cnt++>100) return false;
	int p=city[pos];
	for(;p!=-1;p=mymalloc[p].next)
	{
		if(pos==s) currentstart=mymalloc[p].start;
		if(mymalloc[p].start>=nowtime)
		{
			if(mymalloc[p].des==t)
			{
				if(mymalloc[p].end<=bestend)
				{
					if(mymalloc[p].end==bestend) beststart=beststart>currentstart?beststart:currentstart;
					else
					{
						bestend=mymalloc[p].end;
						beststart=currentstart;
					}
				}
			}
			else
			{
				check[mymalloc[p].des]=true;
				if(!search(mymalloc[p].des,mymalloc[p].end)) return false;
				check[mymalloc[p].des]=false;
			}
		}
	}
	return true;
}
int main()
{
	int tcnt=1;
	while(init())
	{
		printf("Scenario #%d\n",tcnt++);
		beststart=0;
		bestend=2500;
		memset(check,false,sizeof(check));
		check[s]=true;cnt=0;
		search(s,bedtime);
		if(bestend!=2500)
		{
			printf("Departure %04d ",beststart);cout<<from<<endl;
			printf("Arrival   %04d ",bestend);cout<<to<<endl;
		}
		else cout<<"No connection"<<endl;
		cout<<endl;
	}
	return 1;
}






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