Submission #1727701

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair< ll, ll >;

using namespace std;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

struct edge { int to; double cost; };
int n;
vector<edge> G[1010];
double d[1010];

void dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    fill(d, d+n, 1e8);
    d[s] = 0;
    que.push(make_pair(0, s));
    while (!que.empty()) {
        pair<int, int> p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int main() {
    int tx1, ty1, tx2, ty2, T, V;
    cin >> tx1 >> ty1 >> tx2 >> ty2 >> T >> V >> n;
    vector<pair<double, double>> pos(n);
    for (auto & p : pos) {
        cin >> p.first >> p.second;
    }
    rep(i, n) {
        auto& p = pos[i];
        edge e;
        e.to = i+1;
        e.cost = sqrt((tx1-p.first)*(tx1-p.first)+(ty1-p.second)*(ty1-p.second));
        G[0].push_back(e);
        edge e2;
        e2.to = n+1;
        e2.cost = sqrt((tx2-p.first)*(tx2-p.first)+(ty2-p.second)*(ty2-p.second));
        G[e.to].push_back(e2);
        //cout << e.cost << " " << e2.cost << endl;
    }
    n += 2;
    dijkstra(0);
    cout << (T*V >= d[n-1] ? "YES" : "NO") << endl;
}

Submission Info

Judge Result