• <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 拆點+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 閱讀(438) 評論(0)  編輯 收藏 引用 所屬分類: DPgraph

            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            99久久国产亚洲高清观看2024 | 亚洲成色999久久网站| 久久精品国产清高在天天线| 精品久久久久香蕉网| 日本久久久久久中文字幕| 国产高潮国产高潮久久久91 | 香蕉久久夜色精品国产2020| 久久精品日日躁夜夜躁欧美| 久久ww精品w免费人成| 99热热久久这里只有精品68| 亚洲欧美成人久久综合中文网| 精品伊人久久大线蕉色首页| 国内精品久久九九国产精品| 国产精品欧美久久久久无广告| 亚洲精品午夜国产va久久| 996久久国产精品线观看| 久久久久亚洲AV无码专区网站| 精品无码久久久久国产动漫3d| 久久精品一区二区| 亚洲中文字幕无码久久2020| 国产日韩久久免费影院| 久久久久亚洲AV无码网站| 亚洲午夜精品久久久久久浪潮| 99久久中文字幕| 亚洲国产精品成人久久| 久久久中文字幕日本| 国产精品岛国久久久久| 伊人久久成人成综合网222| 久久无码av三级| 国产成人精品白浆久久69| 少妇熟女久久综合网色欲| 欧美精品福利视频一区二区三区久久久精品 | 久久香蕉国产线看观看乱码| 狠狠色丁香久久婷婷综合图片| 97精品国产97久久久久久免费 | 国产AⅤ精品一区二区三区久久| 亚洲AV日韩AV永久无码久久| 综合久久一区二区三区| 四虎国产精品免费久久| 欧美色综合久久久久久| 久久亚洲AV永久无码精品|