QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#958459#2647. Environment-Friendly Travelcartofel24AC ✓225ms14680kbC++142.8kb2025-03-31 00:05:232025-03-31 00:05:30

Judging History

This is the latest submission verdict.

  • [2025-03-31 00:05:30]
  • Judged
  • Verdict: AC
  • Time: 225ms
  • Memory: 14680kb
  • [2025-03-31 00:05:23]
  • Submitted

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'