| ||||||||||
| 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 | |||||||||
我BFS WA了,别人DFS 过了,想不通一点#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator