Submission #4624567
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
const int IINF = 1e9 + 100;
const long long LLINF = 2e18 + 129;
const long long MOD = 1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;
struct node{
int id;
double cost;
bool operator<(const node & right) const {
return cost > right.cost;
}
};
template<typename T>
bool chmin(T &a, T b){
if(a > b){
a = b;
return true;
}else{
return false;
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
double sx, sy, gx, gy;
cin >> sx >> sy >> gx >> gy;
int n;
cin >> n;
vector<double> x(n + 2), y(n + 2), r(n + 2);
x[0] = sx;
y[0] = sy;
r[0] = 0;
x[n + 1] = gx;
y[n + 1] = gy;
r[n + 1] = 0;
REP(i, 1, n + 1){
cin >> x[i] >> y[i] >> r[i];
}
vector<double> cost(n + 2, 1e15);
priority_queue<node> que;
que.push({0, 0.0});
while(!que.empty()){
node now = que.top();
que.pop();
if(!chmin(cost[now.id], now.cost)){
continue;
}
rep(i, n + 2){
double ncost = max(now.cost + sqrt(pow(x[i] - x[now.id], 2.0) + pow(y[i] - y[now.id], 2.0)) - r[i] - r[now.id], 0.0);
if(i != now.id && cost[i] > ncost){
que.push({i, ncost});
}
}
}
cout << fixed << setprecision(12) << cost[n + 1] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Cosmic Rays |
User |
mhrb |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2006 Byte |
Status |
WA |
Exec Time |
979 ms |
Memory |
66148 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
WA |
341 ms |
34536 KB |
1_03.txt |
WA |
269 ms |
33512 KB |
1_04.txt |
AC |
95 ms |
10352 KB |
1_05.txt |
WA |
98 ms |
8688 KB |
1_06.txt |
AC |
88 ms |
10480 KB |
1_07.txt |
AC |
95 ms |
10608 KB |
1_08.txt |
WA |
143 ms |
18796 KB |
1_09.txt |
WA |
322 ms |
34792 KB |
1_10.txt |
AC |
96 ms |
8688 KB |
1_11.txt |
WA |
149 ms |
18284 KB |
1_12.txt |
AC |
96 ms |
10480 KB |
1_13.txt |
AC |
84 ms |
9712 KB |
1_14.txt |
WA |
205 ms |
18540 KB |
1_15.txt |
WA |
979 ms |
66148 KB |
1_16.txt |
WA |
201 ms |
18028 KB |
1_17.txt |
WA |
296 ms |
33512 KB |
1_18.txt |
WA |
159 ms |
18796 KB |
1_19.txt |
WA |
284 ms |
35048 KB |
1_20.txt |
AC |
91 ms |
9328 KB |
1_21.txt |
AC |
94 ms |
9200 KB |
1_22.txt |
WA |
240 ms |
34664 KB |
1_23.txt |
WA |
110 ms |
18540 KB |
1_24.txt |
WA |
232 ms |
34792 KB |
1_25.txt |
WA |
126 ms |
18540 KB |
1_26.txt |
WA |
233 ms |
33640 KB |
1_27.txt |
AC |
95 ms |
8816 KB |
1_28.txt |
WA |
137 ms |
18540 KB |
1_29.txt |
AC |
100 ms |
10608 KB |
1_30.txt |
AC |
93 ms |
10096 KB |
1_31.txt |
AC |
95 ms |
9584 KB |
1_32.txt |
WA |
115 ms |
17772 KB |
1_33.txt |
WA |
249 ms |
34152 KB |
1_34.txt |
AC |
92 ms |
9712 KB |
1_35.txt |
AC |
95 ms |
9456 KB |
1_36.txt |
AC |
95 ms |
10608 KB |
1_37.txt |
AC |
94 ms |
10608 KB |
1_38.txt |
AC |
92 ms |
4724 KB |
1_39.txt |
AC |
92 ms |
5492 KB |
1_40.txt |
AC |
91 ms |
6516 KB |
1_41.txt |
AC |
92 ms |
6004 KB |
1_42.txt |
AC |
88 ms |
9200 KB |
1_43.txt |
AC |
92 ms |
9840 KB |
1_44.txt |
AC |
89 ms |
9200 KB |
1_45.txt |
AC |
90 ms |
8816 KB |