• <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

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

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久伊人精品一区二区三区| 精品无码久久久久国产动漫3d| 一个色综合久久| 久久亚洲AV成人无码软件| 久久人与动人物a级毛片| 久久亚洲欧美国产精品| 69国产成人综合久久精品| 精品久久久久久无码人妻蜜桃| 美女久久久久久| 久久国产乱子伦精品免费强| 久久综合精品国产一区二区三区| 久久经典免费视频| 99久久夜色精品国产网站| 久久综合狠狠综合久久综合88| 久久午夜伦鲁片免费无码| 91精品国产综合久久婷婷| 久久婷婷五月综合色99啪ak| 久久综合噜噜激激的五月天| 香蕉久久夜色精品国产小说| 久久国产色AV免费观看| 久久精品国产亚洲αv忘忧草 | 国产成人综合久久综合| 久久国产香蕉视频| 国产—久久香蕉国产线看观看| 一本色综合久久| 久久久国产精品| 色综合久久88色综合天天| 欧美激情精品久久久久| 久久久久久午夜成人影院| 欧美国产成人久久精品| 久久亚洲精品无码播放| 久久996热精品xxxx| 久久本道久久综合伊人| 久久99久久成人免费播放| 国产精品99久久久久久宅男| 色综合久久久久网| 久久免费精品一区二区| 色综合久久最新中文字幕| 国产精品欧美久久久久天天影视 | 婷婷五月深深久久精品| 97久久精品人妻人人搡人人玩|