2301.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2301 on 2006-08-02 at 19:30:22 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
 
const int N = 1024;
const int INF = 1 << 30;
 
int r[N], rn;
 
class Phone {
public:
	int time, year;
	void make(int);
	void yearM(const Phone&);
	bool cert(const Phone&) const;
};
void Phone::make(int o) {
	int mon, d, h, m; scanf("%d:%d:%d:%d", &mon, &d, &h, &m);
	time = mon*1000000+d*10000+h*100+m;
	char c; scanf("%*s\n%c", &c);
	if(c == '+') r[rn++] = o;
}
void Phone::yearM(const Phone& p) {
	if(p.time > time) year = p.year;
	else year = p.year-1;
}
bool Phone::cert(const Phone& p) const {
	if(p.year-year >= 2) return false;
	else if(p.year-year == 1) return time >= p.time;
	else return time < p.time;
}
 
int step[N], n;
Phone p[N];
 
int bfs(int, int);
 
int main()
{
	int i;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		rn = 0;
		for(i = 0; i < n; i++) p[i].make(i);
		p[n].time = INF; p[n].year = N; n++;
		r[rn++] = n-1;
		for(i = n-2; i >= 0; i--) p[i].yearM(p[i+1]);
		int ct = 0; memset(step, -1, sizeof(step));
		for(i = 0; i < rn-1; i++) ct += bfs(r[i], r[i+1]);
		printf("%d\n", ct);
	}
	
	return 0;
}
 
int bfs(int b, int e)
{
	queue<int> Q; Q.push(b); step[b] = 0;
	int i;
	while(!Q.empty()) {
		int v = Q.front(); Q.pop();
		for(i = e; i > v; i--)
			if(step[i] != -1 || !p[v].cert(p[i])) continue;
			else if(i == e) return step[v]+1;
			else { step[i] = step[v]+1; Q.push(i); }
	}
	return -1;
}