1464.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1464 on 2005-12-26 at 01:26:57 */ 
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

const int MAX = 128;
const int L_MAX = 32;
const int R_MAX = 1024;
const int INF = 20000000;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};	

map<const char*, int, cmp> city;

class Edge {
private:
	class Point {
	public:
		char name[L_MAX];
	};
public:
	Point a, b;
	int bo, eo, bt, et;
	bool make();
};
bool Edge::make() {
	scanf("%s %s %d %d", a.name, b.name, &bt, &et);
	bt = (bt+6)%24; et = bt + et;
	if(et > 12) return false;
	if(city.count(a.name) == 0) bo = city.size(), city[a.name] = bo;
	else bo = city.find(a.name)->second;
	if(city.count(b.name) == 0) eo = city.size(), city[b.name] = eo;
	else eo = city.find(b.name)->second;
	return true;
}

int main()
{
	Edge edge[R_MAX];
	int d[MAX], m;
	int t, T, i, j;
	char sname[MAX], dname[MAX];

	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		int en = 0; city.clear();
		scanf("%d", &m);
		for(i = 0; i < m; i++) {
			if(edge[en].make()) en++;
		}
		int n = city.size();
		for(i = 0; i < n; i++) d[i] = INF;
		scanf("%s %s", sname, dname);
		int sor, dor = -1;
		if(city.count(sname) != 0 && city.count(dname) != 0) {
			sor = city.find(sname)->second, dor = city.find(dname)->second;
			bool ex = true;
			d[sor] = 0;
			for(i = 0; i < n && ex; i++) {
				ex = false;
				for(j = 0; j < en; j++) {
					int a = edge[j].bo, b = edge[j].eo;
					if(d[a] == INF) continue;
					else if(d[a]%24 > edge[j].bt) {
						if(d[b] > (d[a]/24+1)*24+edge[j].et) {
							ex = true;
							d[b] = (d[a]/24+1)*24+edge[j].et;
						}
					} else {
						if(d[b] > d[a]/24*24+edge[j].et) {
							ex = true;
							d[b] = d[a]/24*24+edge[j].et;
						}
					}
				}
			}
		}
		printf("Test Case %d.\n", t);
		if(dor == -1 || d[dor] == INF) printf("There is no route Vladimir can take.\n");
		else printf("Vladimir needs %d litre(s) of blood.\n", d[dor]/24);
	}
	
	return 0;
}