Submission #949671

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

typedef ld Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

void dijkstra(Graph &g, int s, Array &d)
{
	d.assign(g.size(), INF);
	d[s] = 0;
	typedef pair<Weight, int> P;
	priority_queue<P, vector<P>, greater<P>> que;
	que.push(P(0, s));
	while (!que.empty())
	{
		Weight dist = que.top().first;
		int v = que.top().second;
		que.pop();
		if (d[v] < dist) continue;
		REP(i, g[v].size())
		{
			Edge e = g[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}


int n;
vector<ld> x, y, t, r;

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	cin >> n;
	x.resize(n); y.resize(n); t.resize(n); r.resize(n);
	REP(i, n) cin >> x[i] >> y[i] >> t[i] >> r[i];
	Graph g(n);
	REP(i, n)REP(j, n)
	{
		if (i == j) continue;
		ld v = min(t[i], r[j]);
		ld dist = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
		add_edge(g, i, j, dist / v);
	}
	Array d;
	dijkstra(g, 0, d);
	sort(ALL(d));
	REP(i, n - 1) d[n - i - 1] += (ld)i;
	cout << *max_element(ALL(d)) << endl;
	return 0;
}

Submission Info

Judge Result