Submission #32751762

---

Source Code Expand

#include<iostream>
#include<vector>
#include<string>
#include<utility>
#include<algorithm>
#include<queue>
#include<cmath>
#include<functional>

using namespace std;

typedef pair<int, int> P;
typedef long long int llint;

int N;


int main() {
	cin >> N;
	vector<P> xy(N);
	vector<llint> P(N);
	for (int i = 0; i < N; i++) {
		cin >> xy[i].first >> xy[i].second >> P[i];
	}
	vector<vector<llint> > distance(N, vector<llint>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j) { continue; }
			llint man = abs(xy[i].first - xy[j].first) + abs(xy[i].second - xy[j].second);
			distance[i][j] = (man + P[i] - 1) / P[i];
			distance[j][i] = (man + P[i] - 1) / P[j];
		}
	}

	llint ans = 4000000001;
	for (int i = 0; i < N; i++) {
		llint cost = 0;
		vector<bool> used(N, false);
		used[i] = true;
		int use_sum = 1;
		priority_queue<pair<llint, llint>, vector< pair<llint, llint> >, greater<pair<llint, llint> >> que;
		for (int j = 0; j < N; j++) {
			if (i != j) { que.push(make_pair(distance[i][j], j)); }
		}
		while (use_sum < N) {
			pair<llint, llint> next = que.top(); que.pop();
			if (used[next.second]) { continue; }
			used[next.second] = true;
			cost = max(cost, next.first);
			use_sum++;
			//cout << "to:" << next.second << ", cost" << next.first << endl;
			for (int i = 0; i < N; i++) {
				if (!used[i]) {
					que.push(make_pair(distance[next.second][i], i));
				}
			}
		}
	/*	cout << i << ",  " << flush;
		cout << cost << endl;*/
		ans = min(ans, (llint)ceil(cost));
	}
	cout << ans << endl;
}

Submission Info

Judge Result