提出 #47173460

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std; 

int n; 
double xs, ys, xt, yt, x[1005], y[1005], r[1005]; 
double d[1005][1005], f[1005]; 
bool v[1005]; 

inline double calc(double x1, double y1, double x2, double y2) {
    return hypot(x1 - x2, y1 - y2); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> xs >> ys >> xt >> yt; 
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i] >> r[i]; 
    x[0] = xs, y[0] = ys; x[n + 1] = xt; y[n + 1] = yt; 
    for (int i = 0; i <= n + 1; ++i) for (int j = i + 1; j <= n + 1; ++j)
        d[i][j] = d[j][i] = max(0.0, calc(x[i], y[i], x[j], y[j]) - r[i] - r[j]); 
    for (int i = 1; i <= n + 1; ++i) f[i] = 1e18; 
    for (int op = 1; op <= n + 1; ++op) {
        int x = -1; 
        for (int i = 0; i <= n + 1; ++i)
            if (!v[i] && (x == -1 || f[i] < f[x])) x = i; 
        v[x] = 1; 
        // cout << x << "\n"; 
        for (int i = 0; i <= n + 1; ++i)
            f[i] = min(f[i], f[x] + d[x][i]); 
    }
    // printf("%.10lf %.10lf\n", d[0][1], d[1][2]); 
    printf("%.10lf\n", f[n + 1]); 
    return 0; 
}

提出情報

提出日時
問題 E - Cosmic Rays
ユーザ james1BadCreeper
言語 C++ 17 (gcc 12.2)
得点 600
コード長 1127 Byte
結果 AC
実行時間 18 ms
メモリ 11880 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 3
AC × 49
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
0_00.txt AC 1 ms 3940 KiB
0_01.txt AC 1 ms 3904 KiB
0_02.txt AC 1 ms 3904 KiB
1_00.txt AC 1 ms 3940 KiB
1_01.txt AC 1 ms 3960 KiB
1_02.txt AC 14 ms 11704 KiB
1_03.txt AC 14 ms 11740 KiB
1_04.txt AC 14 ms 11728 KiB
1_05.txt AC 15 ms 11784 KiB
1_06.txt AC 16 ms 11648 KiB
1_07.txt AC 14 ms 11608 KiB
1_08.txt AC 15 ms 11780 KiB
1_09.txt AC 14 ms 11652 KiB
1_10.txt AC 14 ms 11828 KiB
1_11.txt AC 14 ms 11668 KiB
1_12.txt AC 14 ms 11608 KiB
1_13.txt AC 18 ms 11744 KiB
1_14.txt AC 15 ms 11728 KiB
1_15.txt AC 15 ms 11844 KiB
1_16.txt AC 15 ms 11724 KiB
1_17.txt AC 14 ms 11764 KiB
1_18.txt AC 15 ms 11736 KiB
1_19.txt AC 15 ms 11840 KiB
1_20.txt AC 16 ms 11792 KiB
1_21.txt AC 14 ms 11696 KiB
1_22.txt AC 15 ms 11792 KiB
1_23.txt AC 14 ms 11768 KiB
1_24.txt AC 15 ms 11772 KiB
1_25.txt AC 14 ms 11656 KiB
1_26.txt AC 15 ms 11664 KiB
1_27.txt AC 14 ms 11624 KiB
1_28.txt AC 15 ms 11688 KiB
1_29.txt AC 15 ms 11756 KiB
1_30.txt AC 15 ms 11736 KiB
1_31.txt AC 15 ms 11732 KiB
1_32.txt AC 15 ms 11828 KiB
1_33.txt AC 14 ms 11708 KiB
1_34.txt AC 14 ms 11660 KiB
1_35.txt AC 15 ms 11880 KiB
1_36.txt AC 15 ms 11744 KiB
1_37.txt AC 14 ms 11764 KiB
1_38.txt AC 9 ms 11840 KiB
1_39.txt AC 9 ms 11816 KiB
1_40.txt AC 10 ms 11740 KiB
1_41.txt AC 9 ms 11816 KiB
1_42.txt AC 11 ms 11696 KiB
1_43.txt AC 11 ms 11840 KiB
1_44.txt AC 10 ms 11752 KiB
1_45.txt AC 11 ms 11800 KiB