QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167347#7184. Transport PlusesMei Dui Yao (Qiuyang Zhang, Jiyu Shen)#ML 1ms4040kbC++141.9kb2023-09-07 13:58:332023-09-07 13:58:33

Judging History

This is the latest submission verdict.

  • [2023-09-07 13:58:33]
  • Judged
  • Verdict: ML
  • Time: 1ms
  • Memory: 4040kb
  • [2023-09-07 13:58:33]
  • Submitted

answer

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
int n, t;
double sx, sy, ex, ey, x[105], y[105];
std::tuple<double, int, double, double> from[105];
bool vis[105];
std::vector<std::tuple<int, double, double>> ans;
void print()
{
    int cur = n + 1;
    ans.push_back({0, ex, ey});
    while (cur)
    {
        ans.push_back({std::get<1>(from[cur]), std::get<2>(from[cur]), std::get<3>(from[cur])});
        cur = std::get<1>(from[cur]);
    }
    std::reverse(ans.begin(), ans.end());
    std::cout << ans.size() << std::endl;
    for (auto i : ans)
        std::cout << std::get<0>(i) << ' ' << std::get<1>(i) << ' ' << std::get<2>(i) << std::endl;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> t >> sx >> sy >> ex >> ey;
    for (int i = 1; i <= n; ++i)
        std::cin >> x[i] >> y[i];
    for (int i = 1; i <= n; ++i)
        from[i] = std::min(std::make_tuple(std::abs(x[i] - sx), 0, x[i], sy),
                           std::make_tuple(std::abs(y[i] - sy), 0, sx, y[i]));
    from[n + 1] = std::make_tuple(std::hypot(sx - ex, sy - ey), 0, ex, ey);
    for (int i = 1; i <= n; ++i)
    {
        int k = n + 1;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && from[j] < from[k])
                k = j;
        if (k == n + 1)
            break;
        vis[k] = true;
        double d = std::get<0>(from[k]);
        for (int j = 1; j <= n; ++j)
            from[j] = std::min(from[j],
                               std::make_tuple(d + t, k, x[k], y[j]));
        from[n + 1] = std::min(from[n + 1],
                               std::min(std::make_tuple(d + t + std::abs(y[k] - ey), k, ex, y[k]),
                                        std::make_tuple(d + t + std::abs(x[k] - ex), k, x[k], ey)));
    }
    std::cout << std::fixed << std::setprecision(10) << std::get<0>(from[n + 1]) << std::endl;
    print();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4040kb

input:

1 2
1 1
5 3
6 2

output:

4.0000000000
3
0 1.0000000000 2.0000000000
1 5.0000000000 2.0000000000
0 5.0000000000 3.0000000000

result:

ok correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

2 1
1 1
6 1
1 3
6 3

output:

2.0000000000
4
0 1.0000000000 1.0000000000
1 1.0000000000 3.0000000000
2 6.0000000000 1.0000000000
0 6.0000000000 1.0000000000

result:

ok correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

0 0
1 1
1 1

output:

0.0000000000
2
0 1.0000000000 1.0000000000
0 1.0000000000 1.0000000000

result:

ok correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

0 0
100 100
0 0

output:

141.4213562373
2
0 0.0000000000 0.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #5:

score: 0
Accepted
time: 1ms
memory: 3972kb

input:

1 0
100 100
0 0
100 100

output:

100.0000000000
3
0 100.0000000000 100.0000000000
1 0.0000000000 100.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #6:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

1 0
100 100
0 0
100 0

output:

0.0000000000
3
0 100.0000000000 100.0000000000
1 0.0000000000 0.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #7:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

1 0
100 100
0 0
0 100

output:

0.0000000000
3
0 100.0000000000 100.0000000000
1 0.0000000000 0.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #8:

score: 0
Accepted
time: 1ms
memory: 4024kb

input:

1 100
50 50
0 0
50 50

output:

70.7106781187
2
0 0.0000000000 0.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #9:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

1 100
50 50
0 0
0 50

output:

70.7106781187
2
0 0.0000000000 0.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #10:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

1 100
50 50
0 0
51 51

output:

70.7106781187
2
0 0.0000000000 0.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

1 100
50 50
0 0
2 53

output:

70.7106781187
2
0 0.0000000000 0.0000000000
0 0.0000000000 0.0000000000

result:

ok correct

Test #12:

score: 0
Accepted
time: 1ms
memory: 4024kb

input:

1 100
0 0
100 100
50 50

output:

141.4213562373
2
0 100.0000000000 100.0000000000
0 100.0000000000 100.0000000000

result:

ok correct

Test #13:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

1 33
0 0
100 100
50 50

output:

133.0000000000
3
0 0.0000000000 50.0000000000
1 50.0000000000 100.0000000000
0 100.0000000000 100.0000000000

result:

ok correct

Test #14:

score: 0
Accepted
time: 1ms
memory: 4020kb

input:

1 12
100 0
11 90
0 100

output:

122.0000000000
3
0 0.0000000000 0.0000000000
1 11.0000000000 100.0000000000
0 11.0000000000 90.0000000000

result:

ok correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

1 12
100 0
10 89
0 100

output:

122.0000000000
3
0 0.0000000000 0.0000000000
1 0.0000000000 89.0000000000
0 10.0000000000 89.0000000000

result:

ok correct

Test #16:

score: 0
Accepted
time: 1ms
memory: 3984kb

input:

2 1
2 1
5 1
1 3
6 3

output:

3.0000000000
2
0 5.0000000000 1.0000000000
0 5.0000000000 1.0000000000

result:

ok correct

Test #17:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

2 2
2 1
5 1
1 3
6 3

output:

3.0000000000
2
0 5.0000000000 1.0000000000
0 5.0000000000 1.0000000000

result:

ok correct

Test #18:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

1 2
1 1
5 3
7 2

output:

4.0000000000
3
0 1.0000000000 2.0000000000
1 5.0000000000 2.0000000000
0 5.0000000000 3.0000000000

result:

ok correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

1 2
1 1
5 4
6 2

output:

4.0000000000
3
0 1.0000000000 2.0000000000
1 6.0000000000 4.0000000000
0 5.0000000000 4.0000000000

result:

ok correct

Test #20:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

12 1
77 80
76 78
77 81
76 79
77 78
75 80
75 79
76 80
78 81
77 81
76 81
76 80
77 79
76 79

output:

1.0000000000
3
0 77.0000000000 80.0000000000
3 76.0000000000 78.0000000000
0 76.0000000000 78.0000000000

result:

ok correct

Test #21:

score: 0
Accepted
time: 1ms
memory: 3972kb

input:

5 1
40 69
37 71
37 69
36 71
38 70
40 72
40 71

output:

1.0000000000
3
0 40.0000000000 69.0000000000
1 37.0000000000 71.0000000000
0 37.0000000000 71.0000000000

result:

ok correct

Test #22:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

8 1
84 27
86 32
85 31
83 27
86 27
85 28
83 27
83 32
85 31
87 29

output:

1.0000000000
3
0 84.0000000000 27.0000000000
3 86.0000000000 32.0000000000
0 86.0000000000 32.0000000000

result:

ok correct

Test #23:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

11 1
95 30
99 36
96 33
95 36
94 30
98 33
98 36
97 31
99 33
99 31
98 35
95 36
100 32

output:

1.0000000000
3
0 95.0000000000 30.0000000000
2 99.0000000000 36.0000000000
0 99.0000000000 36.0000000000

result:

ok correct

Test #24:

score: 0
Accepted
time: 1ms
memory: 4036kb

input:

4 1
19 37
18 32
18 36
21 36
19 33
22 34

output:

2.0000000000
3
0 18.0000000000 37.0000000000
1 18.0000000000 32.0000000000
0 18.0000000000 32.0000000000

result:

ok correct

Test #25:

score: 0
Accepted
time: 1ms
memory: 3972kb

input:

7 1
49 6
48 8
46 3
49 9
45 6
43 3
49 8
43 8
48 2

output:

1.0000000000
3
0 49.0000000000 6.0000000000
5 48.0000000000 8.0000000000
0 48.0000000000 8.0000000000

result:

ok correct

Test #26:

score: -100
Memory Limit Exceeded

input:

10 0
75 31
74 34
77 36
79 34
74 37
75 32
76 31
81 37
79 34
77 28
80 36
80 28

output:

0.0000000000

result: