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
AC × 3
AC × 29
WA × 20
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