PKU 2267 From Dusk till Dawn or: Vladimir the Vampire

• ダイクストラ法
• 時刻の概念があるのでノードに時刻を持たせる必要がある
• 実はUVA時代に生まれて初めて解けたダイクストラ法の問題だったりする

struct Dic {
	map<string, int> m;
	int get(const string& s) {
		if (!m.count(s)) {
			const int index = m.size();
			m[s] = index;
			return index;
		} else {
			return m[s];
		}
	}
};

struct Edge {
	int src, dst, departure, arrival;
};

int main() {
	int numberOfCases;
	cin >> numberOfCases;
	for (int caseIndex = 1; caseIndex <= numberOfCases; ++caseIndex) {
		vector<Edge> edges;
		int M;
		cin >> M;

		Dic dic;
		for (int n = 0; n < M; ++n) {
			Edge edge;
			string src, dst;
			int departure, travellingTime;
			cin >> src >> dst >> departure >> travellingTime;
			edge.src = dic.get(src);
			edge.dst = dic.get(dst);
			departure %= 24;

			bool ok = true;
			for (int t = departure; t <= departure + travellingTime; ++t) {
				if (6 < t % 24 && t % 24 < 18) {
					ok = false;
				}
			}

			if (!ok) {
				continue;
			}

			edge.departure = departure;
			edge.arrival = departure + travellingTime;

			edges.push_back(edge);
		}

		const int N = dic.m.size();

		vector<vector<Edge> > g(N);
		for (vector<Edge>::iterator it = edges.begin(), itEnd = edges.end(); it != itEnd; ++it) {
			g[it->src].push_back(*it);
		}

		string startString;
		cin >> startString;
		const int start = dic.get(startString);

		vector<int> dp(N, INT_MAX);
		dp[start] = 18;

		priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
		q.push(make_pair(18, start));

		while (!q.empty()) {
			const int currentCost = q.top().first;
			const int currentNode = q.top().second;
			q.pop();

			if (dp[currentNode] != currentCost) {
				continue;
			}

			for (vector<Edge>::iterator it = g[currentNode].begin(), itEnd = g[currentNode].end(); it != itEnd; ++it) {
				const Edge& edge = *it;
				int nextCost = currentCost;
				int departure = edge.departure;
				while (nextCost > departure) {
					departure += 24;
				}
				nextCost = departure;
				nextCost += edge.arrival - edge.departure;
				
				const int nextNode = it->dst;
				if (dp[nextNode] > nextCost) {
					dp[nextNode] = nextCost;
					q.push(make_pair(nextCost, nextNode));
				}
			}
		}

		string goalString;
		cin >> goalString;
		const int goal = dic.get(goalString);

		printf("Test Case %d.\n", caseIndex);

		if (dp[goal] == INT_MAX) {
			printf("There is no route Vladimir can take.\n");
		} else {
			int answer = 0;
			for (int t = 36; t < dp[goal]; t += 24) {
				++answer;
			}

			printf("Vladimir needs %d litre(s) of blood.\n", answer);
		}
	}
}