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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年7月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(6)
            


		
            隨筆檔案
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



国产成人无码精品久久久性色|
国内精品久久国产大陆|
久久露脸国产精品|
久久国产欧美日韩精品免费|
久久久久亚洲Av无码专|
国产成人综合久久久久久
|
无码人妻久久久一区二区三区
|
欧美日韩中文字幕久久伊人|
久久久久久A亚洲欧洲AV冫|
亚洲国产欧洲综合997久久|
激情久久久久久久久久|
精品多毛少妇人妻AV免费久久|
精品国产乱码久久久久久1区2区
|
亚洲国产精品无码久久久蜜芽|
99久久婷婷免费国产综合精品|
无码任你躁久久久久久久|
久久久久无码精品国产|
久久无码专区国产精品发布|
韩国三级中文字幕hd久久精品
|
少妇精品久久久一区二区三区
|
国产精品无码久久久久久|
亚洲а∨天堂久久精品|
成人国内精品久久久久影院VR|
97久久国产露脸精品国产|
青青草原综合久久大伊人导航|
99久久精品毛片免费播放|
97久久婷婷五月综合色d啪蜜芽|
久久久久久噜噜精品免费直播|
99久久精品九九亚洲精品|
国产精品99精品久久免费|
久久久久亚洲av无码专区导航
|
久久精品无码专区免费|
亚洲国产精品久久|
久久精品国产久精国产|
97久久超碰国产精品旧版|
国产一区二区三区久久精品|
久久A级毛片免费观看|
久久九九有精品国产23百花影院|
精品国产一区二区三区久久久狼|
男女久久久国产一区二区三区|
久久综合综合久久综合|