QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#167347 | #7184. Transport Pluses | Mei Dui Yao (Qiuyang Zhang, Jiyu Shen)# | ML | 1ms | 4040kb | C++14 | 1.9kb | 2023-09-07 13:58:33 | 2023-09-07 13:58:33 |
Judging History
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