题意：
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
代码：
1
Source 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]!=-1) return 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