PKU 1394 Railroad 题解

最短路径问题。
把每个点出发的所有路都存下
然后每一个点中按每一个路的出发时间降序排序。
然后就做超多遍最短路径就可以了
  1#include<stdio.h>
  2#include<map>
  3#include<string>
  4#include<string.h>
  5#include <stdlib.h>
  6using namespace std;
  7map<string,int>city;
  8struct C{int to,s,t;};
  9C data[100][1000];
 10int l[110],ans[110];
 11char use[110];
 12int cmp(const void * elem1, const void * elem2)
 13{
 14    return  ((struct C*)elem2)->s - ((struct C*)elem1)->s;
 15}
 16int main()
 17{
 18    //freopen("railroad.in","r",stdin);
 19    //freopen("railroad.out","w",stdout);
 20    int SS,TT,n,i,j,k,TTT,TI,s,t,NO,begin,totle,min,KK=0;
 21    string str,S,T;
 22    char name[1000],name1[1000],name2[1000];
 23    while(scanf("%d",&n),n)
 24    {
 25        totle=1000000;
 26        memset(l,0,sizeof(l));
 27        city.clear();
 28        for(i=0;i<n;i++)
 29        {
 30            scanf("%s",name);
 31            str=name;
 32            city[str]=i;
 33        }
 34        scanf("%d",&TTT);
 35        while(TTT--)
 36        {
 37            scanf("%d",&TI);
 38            scanf("%d%s",&s,name);
 39            S=name;SS=city[S];
 40            while(--TI)
 41            {
 42                scanf("%d%s",&t,name);
 43                T=name;TT=city[T];
 44                data[SS][l[SS]].to=TT;
 45                data[SS][l[SS]].s=s;
 46                data[SS][l[SS]].t=t;
 47                l[SS]++;
 48                SS=TT;s=t;
 49            }
 50        }
 51        for(i=0;i<n;i++)qsort(data[i],l[i],sizeof(C),cmp);
 52        /*
 53        for(i=0;i<n;i++)
 54        {
 55            for(j=0;j<l[i];j++)printf("%d ",data[i][j].s);
 56            printf("\n");
 57        }
 58        */
 59        scanf("%d",&s);
 60        scanf("%s",&name1);S=name1;SS=city[S];
 61        scanf("%s",&name2);T=name2;TT=city[T];
 62        for(i=0;i<l[SS];i++)
 63        {
 64            if(data[SS][i].s<s)break;
 65            memset(use,0,sizeof(use));
 66            memset(ans,1,sizeof(ans));
 67            //printf("asdasd%d\n",ans[100]);
 68            ans[SS]=data[SS][i].s;
 69            for(k=1;k<n;k++)
 70            {
 71                min=1000000;
 72                for(j=0;j<n;j++)
 73                    if(!use[j]&&ans[j]!=ans[100]&&ans[j]<min)
 74                    {
 75                        min=ans[j];
 76                        NO=j;
 77                    }
 78                if(min==1000000)break;
 79                use[NO]=1;
 80                for(j=0;j<l[NO];j++)
 81                    if(!use[data[NO][j].to])
 82                    {
 83                        if(data[NO][j].s<ans[NO])break;
 84                        if(data[NO][j].t<ans[data[NO][j].to])ans[data[NO][j].to]=data[NO][j].t;
 85                    }
 86            }
 87            if(ans[TT]<totle)
 88            {
 89                begin=ans[SS];
 90                totle=ans[TT];
 91            }
 92        }
 93        printf("Scenario #%d\n",++KK);
 94        if(totle==1000000)printf("No connection\n");
 95        else 
 96        {
 97            printf("Departure ");
 98            if(begin<1000)printf("0");
 99            else if(begin<100)printf("00");
100            else if(begin<10)printf("000");
101            printf("%d ",begin);
102            printf("%s\n",name1);
103            printf("Arrival   ");
104            begin=totle;
105            if(begin<1000)printf("0");
106            else if(begin<100)printf("00");
107            else if(begin<10)printf("000");
108            printf("%d ",begin);
109            printf("%s\n",name2);
110        }
111        printf("\n");
112    
113    }
114}
115
116

posted on 2008-07-18 16:43 gong 阅读(320) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2008年7月>
日一二三四五六
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜