PKU 2502 Subway

• ダイクストラ法の練習問題として適しています
• 入力がやや厄介かもしれません

typedef complex<double> P;

bool input(P& p) {
	double x, y;
	if (!(cin >> x >> y)) {
		return false;
	}
	p = P(x, y);
	return true;
}

int main() {
	vector<P> positions;
	P p;
	input(p);
	positions.push_back(p);
	input(p);
	positions.push_back(p);

	vector<vector<int> > subways;
	vector<int> subway;
	while (input(p)) {
		if (p.real() < 0) {
			subways.push_back(subway);
			subway.clear();
		} else {
			subway.push_back(positions.size());
			positions.push_back(p);
		}
	}

	const int n = positions.size();
	vector<vector<double> > g(n, vector<double>(n, 1e10));

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			const double r = abs(positions[i] - positions[j]);
			const double t = r / (10.0 * 1000.0 / 60.0);
			g[i][j] = min(g[i][j], t);
		}
	}

	for (vector<vector<int> >::iterator it = subways.begin(); it != subways.end(); ++it) {
		const vector<int>& subway = *it;
		const int m = subway.size();
		for (int i = 0; i + 1 < m; ++i) {
			const int from = subway[i];
			const int to = subway[i + 1];
			const double r = abs(positions[from] - positions[to]);
			const double t = r / (40.0 * 1000.0 / 60.0);
			g[from][to] = min(g[from][to], t);
			g[to][from] = min(g[to][from], t);
		}
	}

	vector<double> dp(n, 1e10);
	dp[0] = 0;
	priority_queue<pair<double, int> > q;
	q.push(make_pair(0, 0));
	while (!q.empty()) {
		const double currentCost = -q.top().first;
		const int currentNode = q.top().second;
		q.pop();
		if (abs(dp[currentNode] - currentCost) > EPS) {
			continue;
		}

		for (int nextNode = 0; nextNode < n; ++nextNode) {
			const double nextCost = currentCost + g[currentNode][nextNode];
			if (dp[nextNode] > nextCost + EPS) {
				dp[nextNode] = nextCost + EPS;
				q.push(make_pair(-dp[nextNode], nextNode));
			}
		}
	}

	cout << (int)(dp[1] + 0.5) << endl;
}