QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#958459 | #2647. Environment-Friendly Travel | cartofel24 | AC ✓ | 225ms | 14680kb | C++14 | 2.8kb | 2025-03-31 00:05:23 | 2025-03-31 00:05:30 |
Judging History
answer
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#define r std::cin
#define w std::cout
const int NMAX = 1e3 + 8;
const int BMAX = 1e2 + 8;
const int TMAX = 1e2 + 8;
int n, b, t;
std::pair<int, int> src, dest;
int src_id, dest_id;
int64_t unit_cost[TMAX];
int64_t x[NMAX], y[NMAX];
int64_t dist[NMAX][NMAX];
int64_t dp[BMAX][NMAX];
struct Edge {
int node;
int type;
Edge(int n, int t) : node(n), type(t){};
};
std::vector<Edge> graph[NMAX];
int64_t compute_dist(int64_t x1, int64_t y1, int64_t x2, int64_t y2)
{
int64_t dx = (x1 - x2);
int64_t dy = (y1 - y2);
return ceil(sqrt(dx * dx + dy * dy));
}
void read()
{
r >> src.first >> src.second;
r >> dest.first >> dest.second;
r >> b;
r >> unit_cost[0];
r >> t;
for (int i = 1; i <= t; ++i) {
r >> unit_cost[i];
}
r >> n;
src_id = n;
dest_id = n + 1;
x[src_id] = src.first;
y[src_id] = src.second;
x[dest_id] = dest.first;
y[dest_id] = dest.second;
for (int i = 0; i < n; ++i) {
r >> x[i] >> y[i];
int links;
r >> links;
while (links--) {
int to, type;
r >> to >> type;
graph[i].emplace_back(to, type);
graph[to].emplace_back(i, type);
}
}
n += 2;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = compute_dist(x[i], y[i], x[j], y[j]);
}
}
for (int i = 0; i < n; ++i) {
graph[src_id].emplace_back(i, 0);
graph[i].emplace_back(src_id, 0);
graph[i].emplace_back(dest_id, 0);
graph[dest_id].emplace_back(i, 0);
}
}
int main()
{
read();
// printf("%d\n", dist[0][3]);
for (int i = 0; i <= b; ++i) {
for (int j = 0; j < n; ++j) {
dp[i][j] = -1;
}
}
// for (int i = 0; i < n; ++i) {
// printf("graph[%d]: ", i);
// for (auto &e : graph[i]) {
// printf("{%d %d}, ", e.node, e.type);
// }
// printf("\n");
// }
// if (b == 45) {
// printf("%ld\n", dp[2][942]);
// }
dp[0][src_id] = 0;
for (int i = 0; i <= b; ++i) {
for (int node = 0; node < n; ++node) {
for (auto &e : graph[node]) {
int km = dist[e.node][node];
if (km > i || dp[i - km][e.node] == -1) {
continue;
}
int64_t cost = unit_cost[e.type] * km;
int64_t cand = dp[i - km][e.node] + cost;
if (dp[i][node] == -1 || cand < dp[i][node]) {
if (b == 45 && ((node == dest_id && i == 7) ||
(node == 942 && i == 2))) {
// printf(
// "dp[%d][%d] = %ld (through dp[%d][%d] km = %d)\n",
// i, node, cand, i - km, e.node, km);
}
dp[i][node] = cand;
}
}
}
}
int64_t ans = -1;
for (int i = 0; i <= b; ++i) {
if (dp[i][dest_id] == -1) {
continue;
}
if (ans == -1 || dp[i][dest_id] < ans) {
ans = dp[i][dest_id];
}
}
w << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
1 1 10 2 12 100 2 10 50 3 2 3 2 1 1 2 2 5 5 1 2 1 9 3 0
output:
850
result:
ok single line: '850'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5872kb
input:
1 1 9 8 10 100 1 1 2 3 5 1 1 1 7 3 1 0 1
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 5 6 3 4 100 2 80 70 4 3 1 3 1 1 3 1 2 1 6 7 2 2 2 3 2 8 2 2 1 2 3 2 11 7 0
output:
400
result:
ok single line: '400'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5740kb
input:
1 3 1 3 4 100 2 80 70 4 3 1 3 1 1 3 1 2 1 6 7 2 2 2 3 2 8 2 2 1 2 3 2 11 7 0
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5744kb
input:
10 2 2 2 12 100 2 10 40 4 2 4 2 1 1 3 2 4 6 1 2 1 9 6 1 3 1 10 4 0
output:
720
result:
ok single line: '720'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
2 2 11 2 20 100 3 50 1 80 2 2 3 2 1 1 1 3 11 3 1 0 2
output:
209
result:
ok single line: '209'
Test #7:
score: 0
Accepted
time: 74ms
memory: 14044kb
input:
17 76 71 92 45 100 100 40 11 29 45 1 34 37 12 37 27 37 19 35 46 14 19 15 10 29 2 31 41 2 43 30 35 21 8 38 27 13 44 22 24 23 22 32 4 12 40 34 33 25 29 48 34 40 31 23 26 46 44 31 17 8 25 13 8 7 22 29 12 39 46 40 34 26 16 26 9 28 31 11 8 25 22 26 39 19 16 6 21 44 24 3 25 29 2 45 39 20 1 24 46 2 36 17 4...
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7780kb
input:
0 0 0 12 15 100 2 1 10 8 0 2 2 2 1 1 2 0 4 1 3 2 8 4 1 3 1 0 6 1 4 2 0 8 2 5 1 6 2 3 10 1 7 1 0 10 1 7 2 0 12 0
output:
300
result:
ok single line: '300'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
0 0 0 12 27 100 2 1 10 8 0 2 2 2 1 1 2 0 4 1 3 2 8 4 1 3 1 0 6 1 4 2 0 8 2 5 1 6 2 3 10 1 7 1 0 10 1 7 2 0 12 0
output:
268
result:
ok single line: '268'
Test #10:
score: 0
Accepted
time: 225ms
memory: 14680kb
input:
56 66 48 89 100 100 100 15 44 28 16 25 37 32 44 43 16 48 3 12 41 32 40 8 45 1 41 3 14 29 43 47 36 32 48 46 18 2 10 18 24 17 35 15 13 30 22 11 17 30 32 4 14 4 14 40 33 41 43 34 48 38 40 20 22 14 3 23 23 24 44 43 11 18 27 11 40 15 37 42 13 7 29 26 36 11 13 32 29 38 11 38 48 4 7 13 1 38 36 14 19 39 12 ...
output:
426
result:
ok single line: '426'
Test #11:
score: 0
Accepted
time: 5ms
memory: 12432kb
input:
0 0 56 52 100 100 10 1 2 3 4 5 6 7 8 9 10 1000 0 0 10 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 9 0 2 9 0 3 9 0 4 9 0 5 9 0 6 9 0 7 9 0 8 9 0 9 9 0 10 9 19 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 11 1 12 2 13 3 14 4 15 5 16 6 17 7 18 8 19 9 20 10 9 17 0 8 17 0 7 17 0 6 17 0 5 17 0 4 17 0 3 17 0 2 17 0...
output:
4656
result:
ok single line: '4656'