• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			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 閱讀(295) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

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

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(6)
            


		
            隨筆檔案
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



av无码久久久久不卡免费网站|
色8激情欧美成人久久综合电|
亚洲av日韩精品久久久久久a|
中文字幕日本人妻久久久免费|
亚洲综合精品香蕉久久网|
色妞色综合久久夜夜|
亚洲一本综合久久|
7777久久久国产精品消防器材|
久久精品无码专区免费青青|
久久国产视频99电影|
日产精品久久久久久久|
久久久久亚洲AV无码去区首|
久久人人爽人人爽人人片AV不|
久久精品国产福利国产琪琪
|
久久国产乱子伦精品免费强|
久久无码精品一区二区三区|
无码伊人66久久大杳蕉网站谷歌|
狠狠色伊人久久精品综合网
|
久久午夜无码鲁丝片秋霞|
久久99精品国产麻豆宅宅|
欧美精品国产综合久久|
久久久久99精品成人片三人毛片
|
久久人与动人物a级毛片|
伊人丁香狠狠色综合久久|
久久国产色AV免费看|
久久久无码精品亚洲日韩蜜臀浪潮
|
久久久久精品国产亚洲AV无码
|
伊人久久免费视频|
久久亚洲私人国产精品|
久久婷婷五月综合97色直播
|
999久久久免费国产精品播放|
日韩人妻无码精品久久久不卡|
久久精品一本到99热免费|
亚洲精品无码专区久久同性男|
国产叼嘿久久精品久久|
久久99国产精品二区不卡|
久久精品成人国产午夜|
久久精品国产69国产精品亚洲|
国产精品久久成人影院|
久久精品国产亚洲网站|
国产精品VIDEOSSEX久久发布|