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