Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
水题 上代码# include <cstdio> # include <set> # include <vector> # include <cstring> # include <iostream> # include <algorithm> using namespace std; struct node { char s[10],e[10]; int nxt; }; int n,m; vector<node> data[100001]; vector<int> l[100001]; int s[100001]; int g[1000005],nxt[2000005],v[2000005],co=0,dp[1000005]; int change(char *ori) { char tmp[10]; strcpy(tmp,ori); return atoi(strtok(tmp,":"))*60+atoi(strtok(NULL,":")); } void addedge(int s,int e) { v[co]=e; nxt[co]=g[s]; g[s]=co++; } int solve(int pos) { if(dp[pos]!=-1) return dp[pos]; else if(g[pos]==-1&&pos>=s[n-1]) return dp[pos]=l[n][pos-s[n-1]]; else { dp[pos]=(pos>=s[n-1]?l[n][pos-s[n-1]]:0xfffffff); for(int p=g[pos];p!=-1;p=nxt[p]) dp[pos]=min(dp[pos],solve(v[p])); return dp[pos]; } } void print(int time) { printf("%s%d:%s%d",time/60<10?"0":"",time/60,time%60<10?"0":"",time%60); } int main() { // freopen("in11","r",stdin); // freopen("ans.txt","w",stdout); scanf("%d",&n); s[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&m); while(m--) { node tmp; scanf("%s%s%d",tmp.s,tmp.e,&tmp.nxt); data[i].push_back(tmp); l[i].push_back(change(tmp.s)); if(tmp.nxt==n) l[n].push_back(change(tmp.e)); } sort(l[i].begin(),l[i].end()); vector<int>::iterator end=unique(l[i].begin(),l[i].end()); while(l[i].end()!=end) l[i].pop_back(); s[i]=s[i-1]+l[i].size(); } memset(g,-1,sizeof(g)); memset(dp,-1,sizeof(dp)); co=0; for(int i=1;i<=n;i++) { for(int j=s[i-1];j<s[i]-1;j++) addedge(j,j+1); for(int j=0;j<data[i].size();j++) 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()) 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()); } vector<pair<int,int> >ans; for(int i=s[1]-1;i>=0;i--) if(solve(i)!=0xfffffff&&(ans.empty()||solve(i)<ans.back().second)) ans.push_back(make_pair(l[1][i],solve(i))); printf("%d\n",ans.size()); for(int i=ans.size()-1;i>=0;i--) { print(ans[i].first); printf(" "); print(ans[i].second); printf("\n"); } // system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator