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

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>
            国产精品网站在线| 久久国产手机看片| 欧美 日韩 国产精品免费观看| 日韩香蕉视频| 亚洲一区视频在线| 先锋影音国产一区| 久久久噜噜噜久久人人看| 欧美一区二区视频观看视频| 亚洲综合首页| 久久免费国产| 欧美日韩成人在线观看| 国产精品人人做人人爽| 国产一区二区三区四区五区美女| 在线日本欧美| 亚洲一区不卡| 久久久高清一区二区三区| 欧美福利视频| 亚洲一区二区三区视频播放| 午夜一级久久| 欧美黄色影院| 欧美视频在线免费| 在线观看欧美一区| 亚洲一级片在线观看| 久久av一区二区三区亚洲| 久久婷婷国产综合国色天香| 日韩一级片网址| 久久久夜色精品亚洲| 欧美午夜欧美| 91久久国产综合久久蜜月精品 | 久久精品国产99精品国产亚洲性色| 久久深夜福利免费观看| 日韩视频永久免费观看| 久久av一区二区三区| 欧美日韩免费看| 在线精品一区二区| 欧美国产日韩视频| 国产精品网曝门| 这里只有精品丝袜| 美女主播精品视频一二三四| 亚洲无线一线二线三线区别av| 免费不卡在线视频| 韩国一区二区在线观看| 亚洲欧美日韩人成在线播放| 亚洲国内高清视频| 欧美一激情一区二区三区| 欧美色中文字幕| 夜夜嗨av一区二区三区四区| 亚洲福利视频免费观看| 久久久亚洲影院你懂的| 国内久久婷婷综合| 久久精品人人| 欧美一区2区三区4区公司二百| 亚洲第一福利视频| 久久久久国产一区二区三区| 国产偷久久久精品专区| 欧美一区亚洲| 亚洲欧美成人一区二区三区| 欧美系列电影免费观看| 一级日韩一区在线观看| 亚洲黄色性网站| 欧美第一黄网免费网站| 91久久精品美女高潮| 欧美成人中文| 欧美成熟视频| 亚洲最新在线视频| 99国产精品一区| 国产精品高潮粉嫩av| 中文在线资源观看网站视频免费不卡| 欧美黄色免费网站| 欧美精品午夜| 亚洲最新在线视频| 亚洲视频自拍偷拍| 国产精品久久久久久久久久妞妞| 午夜国产精品视频| 欧美一区二区久久久| 国产在线日韩| 免费在线亚洲| 欧美高清视频一区| 在线视频精品一区| 亚洲视频专区在线| 国产女人aaa级久久久级| 久久久久久一区二区| 久久综合中文字幕| 一本色道久久综合亚洲91| 亚洲午夜一区二区三区| 国产一级久久| 亚洲高清激情| 国产精品欧美日韩久久| 久久综合九色99| 欧美精品久久久久久久免费观看 | 男女激情久久| 欧美色另类天堂2015| 久久久噜噜噜久噜久久| 欧美成人午夜激情在线| 亚洲免费在线观看| 久久久欧美精品sm网站| 欧美在线播放| 91久久精品www人人做人人爽 | 国产精品国产精品国产专区不蜜| 欧美一区2区三区4区公司二百 | 毛片基地黄久久久久久天堂 | 欧美另类一区二区三区| 亚洲欧美久久久| 久久久久久久网| 国产精品99久久久久久宅男| 欧美中文在线视频| 一本综合久久| 久久美女性网| 午夜精品福利一区二区蜜股av| 久久精品主播| 亚洲欧美国产高清va在线播| 久久综合一区| 久久久久国产精品午夜一区| 欧美日韩成人一区二区| 久久久久久久久久看片| 国产精品久久久久久福利一牛影视| 久热精品视频| 国产精品免费久久久久久| 亚洲日本乱码在线观看| 在线观看欧美日本| 亚洲欧美中日韩| 亚洲少妇在线| 欧美国产专区| 久久综合伊人| 国产亚洲aⅴaaaaaa毛片| 亚洲网站在线| 亚洲一区免费观看| 欧美精品一区在线| 欧美激情aⅴ一区二区三区| 国产一区二区三区久久久| 一区二区欧美视频| 一本大道av伊人久久综合| 欧美激情影音先锋| 欧美激情一区二区三区成人| 亚洲高清中文字幕| 久久网站免费| 欧美成人自拍视频| 在线精品国精品国产尤物884a| 久久久国产精品一区二区中文| 久久国内精品视频| 国产欧美日韩麻豆91| 宅男66日本亚洲欧美视频| 亚洲网站在线播放| 欧美日本一道本| 亚洲精品久久久久久一区二区| 亚洲人成小说网站色在线| 久久看片网站| 欧美国产大片| 亚洲人成啪啪网站| 欧美高清视频在线播放| 欧美成人在线免费观看| 在线观看亚洲专区| 久久人人爽人人爽爽久久| 久久一区二区三区四区五区| 国产区日韩欧美| 久久久一本精品99久久精品66| 欧美日韩国产系列| 久久久久国产精品午夜一区| 欧美日韩裸体免费视频| 一区二区三区日韩欧美| 欧美成人中文字幕| 亚洲国产视频一区| 亚洲天堂网在线观看| 欧美三级电影大全| 亚洲一级影院| 午夜精品久久久久久99热软件| 国产精品天天摸av网| 久久国产主播| 亚洲三级免费| 亚洲欧美在线一区二区| 精品99一区二区| 欧美三级电影一区| 午夜精品国产| 欧美激情一区三区| 午夜国产精品影院在线观看| 一区二区视频在线观看| 欧美日韩国产影院| 欧美在线观看日本一区| 亚洲承认在线| 亚洲欧美日产图| 91久久久精品| 国产免费亚洲高清| 麻豆91精品91久久久的内涵| 亚洲欧洲综合另类| 欧美一区二区三区另类 | 韩国精品一区二区三区| 男女av一区三区二区色多| 亚洲午夜精品久久久久久app| 欧美a级片网| 久久狠狠亚洲综合| 一本大道久久精品懂色aⅴ| 国产九九精品视频| 欧美国产精品v| 欧美在线看片a免费观看| 日韩西西人体444www| 欧美大片网址| 久久日韩粉嫩一区二区三区| 亚洲一品av免费观看| 亚洲人成久久| 一色屋精品视频在线观看网站|