Submission #8808076
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n"
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
const long double pi = acos(-1);
const long double eps = 1e-10;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
using P = pair<double, int>;
int main() {
init();
double sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
int n; cin >> n;
n += 2;
vector<double> x(n), y(n), r(n);
x[0] = sx, y[0] = sy;
x[n - 1] = tx, y[n - 1] = ty;
FOR(i, 1, n - 1)cin >> x[i] >> y[i] >> r[i];
vector<vector<P>> g(n);
FOR(i, 0, n)FOR(j, i + 1, n) {
double dx = x[i] - x[j], dy = y[i] - y[j];
double cost = sqrt(dx * dx + dy * dy);
cost = max(cost - r[i] - r[j], 0.0);
g[i].emplace_back(cost, j);
g[j].emplace_back(cost, i);
}
vector<double> dis(n, LLINF);
priority_queue<P, vector<P>, greater<P>> dik;
dis[0] = 0.0;
dik.emplace(0.0, 0);
while (!dik.empty()) {
double d; int now;
tie(d, now) = dik.top(); dik.pop();
if (dis[now] < d)continue;
for (P next : g[now]) {
double cost; int to;
tie(cost, to) = next;
if (!chmin(dis[to], dis[now] + cost))continue;
dik.emplace(dis[to], to);
}
}
cout << dis[n - 1] << "\n";
}
Submission Info
Submission Time |
|
Task |
E - Cosmic Rays |
User |
first_vil |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
2983 Byte |
Status |
AC |
Exec Time |
105 ms |
Memory |
22548 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
1 ms |
256 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
1 ms |
256 KB |
1_01.txt |
AC |
1 ms |
256 KB |
1_02.txt |
AC |
22 ms |
16640 KB |
1_03.txt |
AC |
23 ms |
17020 KB |
1_04.txt |
AC |
20 ms |
16768 KB |
1_05.txt |
AC |
23 ms |
17184 KB |
1_06.txt |
AC |
20 ms |
16384 KB |
1_07.txt |
AC |
20 ms |
16512 KB |
1_08.txt |
AC |
23 ms |
17020 KB |
1_09.txt |
AC |
23 ms |
16896 KB |
1_10.txt |
AC |
21 ms |
16768 KB |
1_11.txt |
AC |
22 ms |
16656 KB |
1_12.txt |
AC |
22 ms |
16892 KB |
1_13.txt |
AC |
20 ms |
16640 KB |
1_14.txt |
AC |
23 ms |
17184 KB |
1_15.txt |
AC |
24 ms |
17184 KB |
1_16.txt |
AC |
22 ms |
16912 KB |
1_17.txt |
AC |
23 ms |
17184 KB |
1_18.txt |
AC |
23 ms |
17040 KB |
1_19.txt |
AC |
24 ms |
17184 KB |
1_20.txt |
AC |
20 ms |
16512 KB |
1_21.txt |
AC |
21 ms |
16640 KB |
1_22.txt |
AC |
23 ms |
17184 KB |
1_23.txt |
AC |
22 ms |
17184 KB |
1_24.txt |
AC |
23 ms |
17184 KB |
1_25.txt |
AC |
22 ms |
16800 KB |
1_26.txt |
AC |
24 ms |
17020 KB |
1_27.txt |
AC |
22 ms |
16928 KB |
1_28.txt |
AC |
23 ms |
17148 KB |
1_29.txt |
AC |
23 ms |
17184 KB |
1_30.txt |
AC |
20 ms |
16512 KB |
1_31.txt |
AC |
20 ms |
16640 KB |
1_32.txt |
AC |
23 ms |
17168 KB |
1_33.txt |
AC |
23 ms |
16640 KB |
1_34.txt |
AC |
22 ms |
16256 KB |
1_35.txt |
AC |
20 ms |
16512 KB |
1_36.txt |
AC |
20 ms |
16512 KB |
1_37.txt |
AC |
19 ms |
16384 KB |
1_38.txt |
AC |
105 ms |
22548 KB |
1_39.txt |
AC |
105 ms |
22548 KB |
1_40.txt |
AC |
103 ms |
21908 KB |
1_41.txt |
AC |
105 ms |
22420 KB |
1_42.txt |
AC |
22 ms |
16892 KB |
1_43.txt |
AC |
24 ms |
17184 KB |
1_44.txt |
AC |
22 ms |
17184 KB |
1_45.txt |
AC |
27 ms |
17692 KB |