记录编号	86589	评测结果	AAAAAAAAAA
题目名称	[CTSC 2000]公路巡逻	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.001 s
提交时间	2014-01-26 21:20:32	内存使用	20.09 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<vector>
using namespace std;
const int SIZEN=60,SIZEM=310,INF=0x7fffffff/2;
int n[SIZEM]={0},T[SIZEM]={0},t[SIZEM]={0};
int N,M;
int realsecond(int x){//x为时分秒格式,转化为这一天的第几秒
	int hr=(x/10000)%100,mi=(x/100)%100,se=x%100;
	return hr*3600+mi*60+se;
}
int stdtime(int x){//把这一天的第几秒转化为时分秒格式
	int ans=0;
	ans+=(x%60),x/=60;
	ans+=(x%60)*100,x/=60;
	ans+=(x%60)*10000;
	return ans;
}
void printtime(int x){cout<<setw(6)<<setfill('0')<<stdtime(x);}
int f[SIZEN][86400]={0};
int W(int x,int stime,int etime){//stime从x出发,etime到达x+1遇到的巡逻车数量
	int sum=0;
	for(int i=1;i<=M;i++){
		if(n[i]!=x) continue;
		if(T[i]==stime){//同时出发
			if(T[i]+t[i]==etime) sum++;
			continue;
		}
		if(T[i]<stime){//巡逻车在目标之前出发
			if(T[i]+t[i]>=etime) sum++;
		}
		else{//巡逻车在目标之后出发
			if(T[i]+t[i]<=etime) sum++;
		}
	}
	return sum;
}
int ltm[SIZEN]={0},htm[SIZEN]={0};//到达某个点的最早/最晚时间
void DP(void){
	for(int i=1;i<=N;i++){
		ltm[i]=realsecond(60000)+300*(i-1);
		htm[i]=ltm[i]+300*(i-1);
	}
	for(int i=1;i<=N;i++){
		int temp=realsecond(60000)+600*i-300;
		for(int j=realsecond(60000)+300*i-600;j<=temp;j++) f[i][j]=INF;
	}
	f[1][realsecond(60000)]=0;
	for(int i=2;i<=N;i++){
		for(int T=ltm[i];T<=htm[i];T++){
			for(int k=300;k<=600;k++){
				if(f[i-1][T-k]==INF) continue;
				f[i][T]=min(f[i][T],f[i-1][T-k]+W(i-1,T-k,T));
				if(!f[i][T]) break;
			}
		}
	}
	int best=INF;
	for(int i=ltm[N];i<=htm[N];i++) best=min(best,f[N][i]);
	cout<<best<<endl;
	for(int i=ltm[N];i<=htm[N];i++){
		if(f[N][i]==best){
			printtime(i);cout<<endl;
			break;
		}
	}
}
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++){
		scanf("%d",&n[i]);
		string str;
		cin>>str;
		int temp=0;
		for(int j=0;j<6;j++) temp=temp*10+str[j]-'0';
		T[i]=realsecond(temp);
		scanf("%d",&t[i]);
	}
}
int main(){
	freopen("patrol.in","r",stdin);
	freopen("patrol.out","w",stdout);
	read();
	DP();
	return 0;
}