青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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

<2008年7月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

導航

統計

常用鏈接

留言簿(6)

隨筆檔案

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            在线免费不卡视频| 亚洲电影毛片| 亚洲欧美电影在线观看| 久久久在线视频| 日韩亚洲精品视频| 美女成人午夜| 久久精品国产亚洲精品| 99精品欧美| 妖精视频成人观看www| 亚洲第一福利在线观看| 亚洲激精日韩激精欧美精品| 亚洲日本成人女熟在线观看| 亚洲免费激情| 亚洲手机在线| 快射av在线播放一区| 欧美国产专区| 亚洲网站在线播放| 久久国产欧美日韩精品| 欧美成人免费大片| 国产精品久久久| 亚洲国产精品久久久久秋霞不卡 | 久久精品国产99国产精品澳门| 久久精品水蜜桃av综合天堂| 亚洲一区自拍| 国模套图日韩精品一区二区| 欧美一区二区三区喷汁尤物| 欧美成人午夜视频| 国产一区二区精品久久| 午夜精品福利在线观看| 亚洲精品韩国| 久久网站免费| 黄色成人片子| 欧美3dxxxxhd| 久久亚洲图片| 一区二区日韩精品| 亚洲免费电影在线| 国产精品xvideos88| 日韩视频中文字幕| 亚洲人成高清| 欧美日韩性生活视频| 亚洲精品中文字幕女同| 一区二区三区精品视频在线观看| 噜噜噜久久亚洲精品国产品小说| 欧美日韩精品三区| 一本色道久久综合狠狠躁篇的优点| 亚洲精品综合久久中文字幕| 女仆av观看一区| 亚洲大胆人体在线| 亚洲精品孕妇| 欧美日韩国产丝袜另类| 亚洲日本欧美在线| 一区二区免费在线视频| 欧美亚洲综合在线| 国产精品国内视频| 亚洲夜间福利| 久久久久久网| 亚洲另类视频| 国产精品theporn| 欧美一区二区三区免费观看| 久久精品人人| 亚洲国产婷婷香蕉久久久久久99| 欧美日韩一级大片网址| 午夜久久tv| 国产精品高潮在线| 亚洲一区二区三区三| 99re亚洲国产精品| 欧美黄色小视频| 亚洲国产一区二区精品专区| 在线播放国产一区中文字幕剧情欧美| 亚洲午夜免费视频| 欧美一区二区在线播放| 国产乱码精品一区二区三| 亚洲午夜精品久久久久久app| 一区二区三区黄色| 国产精品a级| 亚洲一区久久久| 欧美亚洲在线| 99re国产精品| 久久综合九色| 国产精品99久久久久久久久| 国产情人综合久久777777| 欧美电影电视剧在线观看| 午夜精品电影| 亚洲免费一在线| 欧美三级免费| 欧美激情第一页xxx| 日韩亚洲不卡在线| 欧美日韩中文在线| 欧美在线视频导航| 欧美激情一区二区三区在线视频观看| 国产日韩欧美二区| 亚洲裸体俱乐部裸体舞表演av| 久久午夜av| 亚洲一区在线直播| 欧美黄色一区二区| 西西人体一区二区| 亚洲国产日韩欧美在线99| 欧美日本一道本| 久久久久久久一区| 午夜国产欧美理论在线播放| 亚洲电影有码| 久久综合狠狠综合久久综青草| 亚洲欧洲另类国产综合| 国产精品乱看| 欧美午夜视频网站| 欧美激情a∨在线视频播放| 亚洲性av在线| 一本色道久久综合亚洲精品婷婷 | 国产有码在线一区二区视频| 久久在线91| 久久天天综合| 欧美中文在线观看国产| 亚洲午夜精品一区二区| 亚洲免费大片| 一区二区免费在线观看| 99成人精品| 一区二区免费在线观看| 一区二区精品在线| 中日韩美女免费视频网站在线观看| 亚洲国产小视频在线观看| 亚洲高清一区二| 91久久在线观看| 夜夜躁日日躁狠狠久久88av| 亚洲最快最全在线视频| 亚洲精品一区二区三区99| 亚洲精品免费一二三区| 亚洲精选视频免费看| 一区二区高清视频在线观看| 在线视频欧美日韩精品| 午夜宅男久久久| 欧美电影专区| 日韩一级视频免费观看在线| 亚洲一区二区三区精品动漫| 欧美一区二区三区视频在线 | 嫩草影视亚洲| 亚洲自拍偷拍色片视频| 久久午夜电影网| 国产亚洲免费的视频看| 亚洲精品网址在线观看| 亚洲综合导航| 亚洲精品在线电影| 久久久久久亚洲精品杨幂换脸| 欧美大片免费看| 伊人色综合久久天天五月婷| 亚洲女女女同性video| 欧美aa国产视频| 欧美在线一区二区三区| 国产精品播放| av成人免费观看| 欧美黄色一区二区| 久久久亚洲欧洲日产国码αv| 国产精品久久一区主播| 日韩一级网站| 亚洲日本中文字幕免费在线不卡| 欧美在线一区二区三区| 好吊一区二区三区| 久久婷婷蜜乳一本欲蜜臀| 亚洲一区观看| 国产在线视频不卡二| 久久精彩视频| 久久久欧美一区二区| 亚洲欧洲精品天堂一级| 欧美国产欧美综合| 欧美精品在线视频观看| 中文欧美字幕免费| 午夜精品福利一区二区蜜股av| 国产精品欧美日韩| 久久综合久久综合久久综合| 久久视频精品在线| 亚洲精品在线电影| 午夜精彩视频在线观看不卡 | 欧美日本一道本| 欧美一区二区三区视频在线观看| 欧美一区二区三区四区视频| 在线观看欧美日韩国产| 亚洲三级影片| 韩国av一区二区三区在线观看| 久久夜色精品国产| 久久久国产成人精品| 亚洲一区二区精品视频| 黄色精品网站| 另类天堂视频在线观看| 亚洲视频高清| 欧美顶级艳妇交换群宴| 欧美风情在线观看| 国产女精品视频网站免费| 亚洲视频精选| 亚洲精美视频| 欧美三级网址| 亚洲一区二区三区乱码aⅴ蜜桃女| 欧美1区免费| 国产精品久久久久aaaa九色| 狠狠色香婷婷久久亚洲精品| 一本一道久久综合狠狠老精东影业| 久久蜜桃精品| 久久精品中文字幕一区| 狠狠久久综合婷婷不卡| 久久久一区二区三区| 一本大道av伊人久久综合| 欧美成人福利视频|