2038.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2038 on 2006-05-27 at 09:17:59 */ 
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int N = 1024;

class Visitor {
public:
	int b, it;
	vector<int> vst;
	void make();
	int next() { return vst[++it]; }
};
void Visitor::make() {
	int n, i; scanf("%d %d", &b, &n);
	vst.clear();
	for(i = 0; i < n; i++) {
		int a; scanf("%d", &a);
		vst.push_back(a-1);
	}
	vst.push_back(-1); it = -1;
}

int main()
{
	int i, t, T;
	int n, m, doc[N];
	Visitor v[N];
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &n, &m);
		priority_queue< pii, vector<pii>, greater<pii> > Q;
		memset(doc, -1, sizeof(doc));
		for(i = 0; i < n; i++) {
			v[i].make();
			Q.push(pii(v[i].b-1, i));
		}
		int last;
		while(!Q.empty()) {
			pii p = Q.top(); Q.pop();
			int t = p.first+1, o = p.second, dn = v[o].next();
			if(dn == -1) last = t;
			else {
				doc[dn] = max(doc[dn]+1, t);
				Q.push(pii(doc[dn], o)); 
			}
		}
		printf("%d\n", last);
	}
	
	return 0;
}