• <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 1203 Timetable 拆點(diǎn)+DP最短路

            題意:
            Timetable
            Time Limit: 3000MS  Memory Limit: 65536K
            Total Submissions: 281  Accepted: 86

            Description

            You are the owner of a railway system between n cities, numbered by integers from 1 to n. Each train travels from the start station to the end station according to a very specific timetable (always on time), not stopping anywhere between. On each station a departure timetable is available. Unfortunately each timetable contains only direct connections. A passenger that wants to travel from city p to city q is not limited to direct connections however -- he or she can change trains. Each change takes zero time, but a passenger cannot change from one train to the other if it departs before the first one arrives. People would like to have a timetable of all optimal connections. A connection departing from city p at A o'clock and arriving in city q at B o'clock is called optimal if there is no connection that begins in p not sooner than at A and ends in q not later than at B. We are only interested in connections that can be completed during same day.
            Write a program that:
            reads the number n and departure timetable for each of n cities from the standard input,
            creates a timetable of optimal connections from city 1 to city n,
            writes the answer to the standard output.
            Input

            The first line of the input contains an integer n (2 <= n <= 100000). The following lines contain n timetables for cities 1, 2, ..., n respectively.

            The first line of the timetable description contains only one integer m. Each of the following m lines corresponds to one position in the timetable and contains: departure time A, arrival time B (A < B) and destination city number t (1 <= t <= n) separated by single spaces. Departure time A and arrival time B are written in format hh:mm, where hh are two digits representing full hours (00 <= hh <= 23) and mm are two digits representing minutes (00 <= mm <= 59). Positions in the timetable are given in non-decreasing order according to the departure times. The number of all positions in all timetables does not exceed 1000000.

            Output

            The first line of the output contains an integer r -- the number of positions in the timetable being the solution. Each of the following r lines contains a departure time A and an arrival time B separated by single space. The time format should be like in the input and positions in the timetable should be ordered increasingly according to the departure times. If there is more then one optimal connection with the same departure and arrival time, your program should output just one.
            Sample Input

            3
            3
            09:00 15:00 3
            10:00 12:00 2
            11:00 20:00 3
            2
            11:30 13:00 3
            12:30 14:00 3
            0
            Sample Output

            2
            10:00 14:00
            11:00 20:00
            Hint

            Huge input data, use scanf instead of cin to avoid time limit exceed.
            Source

            Southwestern Europe 2002

            代碼:

              1Source Code
              2
              3Problem: 1203  User: yzhw 
              4Memory: 36324K  Time: 1485MS 
              5Language: G++  Result: Accepted 
              6
              7Source Code 
              8# include <cstdio>
              9# include <set>
             10# include <vector>
             11# include <cstring>
             12# include <iostream>
             13# include <algorithm>
             14using namespace std;
             15struct node
             16{
             17    char s[10],e[10];
             18    int nxt;
             19}
            ;
             20int n,m;
             21vector<node> data[100001];
             22vector<int> l[100001];
             23int s[100001];
             24int g[1000005],nxt[2000005],v[2000005],co=0,dp[1000005];
             25int change(char *ori)
             26{
             27    char tmp[10];
             28    strcpy(tmp,ori);
             29    return atoi(strtok(tmp,":"))*60+atoi(strtok(NULL,":"));
             30}

             31void addedge(int s,int e)
             32{
             33    v[co]=e;
             34    nxt[co]=g[s];
             35    g[s]=co++;
             36}

             37int solve(int pos)
             38{
             39    if(dp[pos]!=-1return dp[pos];
             40    else if(g[pos]==-1&&pos>=s[n-1]) return dp[pos]=l[n][pos-s[n-1]];
             41    else
             42    {
             43        dp[pos]=(pos>=s[n-1]?l[n][pos-s[n-1]]:0xfffffff);
             44        for(int p=g[pos];p!=-1;p=nxt[p])
             45            dp[pos]=min(dp[pos],solve(v[p]));
             46        return dp[pos];
             47        
             48    }

             49}

             50void print(int time)
             51{
             52    printf("%s%d:%s%d",time/60<10?"0":"",time/60,time%60<10?"0":"",time%60);
             53}

             54int main()
             55{
             56  //  freopen("in11","r",stdin);
             57  //  freopen("ans.txt","w",stdout);
             58    scanf("%d",&n);
             59    s[0]=0;
             60    for(int i=1;i<=n;i++)
             61    {
             62        scanf("%d",&m);
             63        while(m--)
             64        {
             65            node tmp;
             66            scanf("%s%s%d",tmp.s,tmp.e,&tmp.nxt);
             67            data[i].push_back(tmp);
             68            l[i].push_back(change(tmp.s));
             69            if(tmp.nxt==n) l[n].push_back(change(tmp.e));
             70        }

             71        sort(l[i].begin(),l[i].end());
             72        vector<int>::iterator end=unique(l[i].begin(),l[i].end());
             73        while(l[i].end()!=end) l[i].pop_back();
             74        s[i]=s[i-1]+l[i].size();
             75    }

             76    memset(g,-1,sizeof(g));
             77    memset(dp,-1,sizeof(dp));
             78    co=0;
             79    for(int i=1;i<=n;i++)
             80    {
             81        for(int j=s[i-1];j<s[i]-1;j++)
             82             addedge(j,j+1);
             83        for(int j=0;j<data[i].size();j++)
             84            if(lower_bound(l[data[i][j].nxt].begin(),l[data[i][j].nxt].end(),change(data[i][j].e))!=l[data[i][j].nxt].end())
             85                addedge(s[i-1]+lower_bound(l[i].begin(),l[i].end(),change(data[i][j].s))-l[i].begin(),s[data[i][j].nxt-1]+lower_bound(l[data[i][j].nxt].begin(),l[data[i][j].nxt].end(),change(data[i][j].e))-l[data[i][j].nxt].begin());
             86
             87    }

             88    vector<pair<int,int> >ans;
             89    for(int i=s[1]-1;i>=0;i--)
             90        if(solve(i)!=0xfffffff&&(ans.empty()||solve(i)<ans.back().second))
             91            ans.push_back(make_pair(l[1][i],solve(i)));
             92    printf("%d\n",ans.size());
             93    for(int i=ans.size()-1;i>=0;i--)
             94    {
             95        print(ans[i].first);
             96        printf(" ");
             97        print(ans[i].second);
             98        printf("\n");
             99    }

            100//    system("pause");
            101    return 0;
            102    
            103}

            104
            105

            posted on 2010-12-09 21:25 yzhw 閱讀(441) 評(píng)論(0)  編輯 收藏 引用 所屬分類: DP 、graph

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導(dǎo)航

            統(tǒng)計(jì)

            公告

            統(tǒng)計(jì)系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            久久国产免费直播| 国产综合成人久久大片91| 亚洲国产成人久久笫一页| 国内精品久久久久久99蜜桃| 久久精品国产男包| 亚洲伊人久久综合影院| 香港aa三级久久三级老师2021国产三级精品三级在 | 久久强奷乱码老熟女网站| 91久久精品视频| 99精品久久久久久久婷婷| 青青草国产精品久久| 久久国产精品-久久精品| 狠狠88综合久久久久综合网| 国产亚洲综合久久系列| 国内精品久久国产大陆| 青青草国产精品久久久久| 国产精品永久久久久久久久久| 久久99国产精品久久久| 色综合久久最新中文字幕| 国产亚洲成人久久| 久久亚洲中文字幕精品一区| 亚洲&#228;v永久无码精品天堂久久 | 777米奇久久最新地址| 一本久久a久久精品综合夜夜| 国产精品久久精品| 99久久精品免费看国产免费| 久久久久九九精品影院| 中文精品99久久国产| 无码精品久久久久久人妻中字| 久久综合给久久狠狠97色 | 国产精品久久久久久久午夜片 | 亚洲国产小视频精品久久久三级| 综合久久一区二区三区 | 国产视频久久| 欧洲国产伦久久久久久久| 久久久无码精品亚洲日韩京东传媒| 日日噜噜夜夜狠狠久久丁香五月 | 人人狠狠综合久久亚洲高清| 久久午夜福利无码1000合集| 久久99精品久久久久婷婷| 九九久久精品无码专区|