QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#834183#2647. Environment-Friendly Travelwhat_a_nameAC ✓61ms20512kbC++143.0kb2024-12-27 12:54:242024-12-27 12:54:25

Judging History

你现在查看的是最新测评结果

  • [2024-12-27 12:54:25]
  • 评测
  • 测评结果:AC
  • 用时:61ms
  • 内存:20512kb
  • [2024-12-27 12:54:24]
  • 提交

answer

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

#define int long long
#define N 1010
#define M 200010
int head[N],nxt[M],e[M];
int val[M];
int sy[M];
int tot = 0;
void addedge(int x,int y,int z,int k) {
	nxt[++tot] = head[x];
	head[x] = tot;
	e[tot] = y;
	val[tot] = z;
	sy[tot] = k;
}

int a,b;
int c,d;
int dismax;

int T;
int pf[N];

int n;
#define PII pair<int,int>
PII pos[N];
vector<PII> lb[N];

int dis[N][N];

int ad[N]; // 额外距离
#define PIP pair<int,PII>
priority_queue<PIP,vector<PIP>,greater<>> q;
bitset<N> v[N];
void Dijkstra() {
	while(!q.empty()) {
		PIP tmp = q.top();
		q.pop();
		int x = tmp.second.first;
		int di = tmp.second.second;
		if(v[x][di]) continue;
		v[x][di] = 1;
		for(int i = head[x];i;i = nxt[i]) {
			int y = e[i];
			// cout << x << " " << y << " " << val[i] << " " << di << " " << ad[y] << '\n';
			if(val[i] + di + ad[y] <= dismax) {
				// cout <<  x << " " << y << '\n';
				if(dis[y][di + val[i]] > dis[x][di] + val[i] * pf[sy[i]]) {
					// cout << x << " " << y << '\n';
					dis[y][di + val[i]] = dis[x][di] + val[i] * pf[sy[i]];
					q.push({dis[y][di + val[i]],{y,di + val[i]}});
				}
			}
		}
	}
}


signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> a >> b >> c >> d;
	cin >> dismax >> pf[0];
	cin >> T;
	for(int i = 1;i <= T; ++i) {
		cin >> pf[i];
	}
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> pos[i].first >> pos[i].second;
		int t;
		cin >> t;
		for(int j = 1; j <= t; ++j) {
			PII tmp;
			cin >> tmp.first >> tmp.second;
			++tmp.first; // 不是,怎么从 0 起
			lb[i].emplace_back(tmp);
		}
	}
	for(int i = 1; i <= n; ++i) {
		// (pos[i].first - c) * (pos[i].first - c) + (pos[i].second - d) * (pos[i].second - d)
		ad[i] = ceil(sqrt((pos[i].first - c) * (pos[i].first - c) + (pos[i].second - d) * (pos[i].second - d)));
		for(auto tmp : lb[i]) {
			int x = tmp.first;
			int y = tmp.second;
			// (pos[i].first - pos[x].first) * (pos[i].first - pos[x].first) + (pos[i].second - pos[x].second) * (pos[i].second - pos[x].second)
			int dis = ceil(sqrt((pos[i].first - pos[x].first) * (pos[i].first - pos[x].first) + (pos[i].second - pos[x].second) * (pos[i].second - pos[x].second)));
			addedge(i,x,dis,y);
			addedge(x,i,dis,y);
			// cout << i << " " << x << '\n';
		}
	}
	memset(dis,0x3f,sizeof(dis));
	for(int i = 1; i <= n; ++i) {
		// (pos[i].first - a) * (pos[i].first - a) + (pos[i].second - b) * (pos[i].second - b)
		int di = ceil(sqrt((pos[i].first - a) * (pos[i].first - a) + (pos[i].second - b) * (pos[i].second - b)));
		dis[i][di] = di * pf[0];
		q.push({dis[i][di],{i,di}});
	}
	int ans = 0x3f3f3f3f3f3f3f3f;
	Dijkstra();
	if(sqrt((a - c) * (a - c) + (b - d) * (b - d)) > dismax) {
		cout << -1;
		return 0;
	}
	ans = ceil(sqrt((a - c) * (a - c) + (b - d) * (b - d))) * pf[0];
	for(int i = 1; i <= n; ++i) {
		for(int j = 0;j + ad[i] <= dismax; ++j) {
			ans = min(ans,dis[i][j] + pf[0] * ad[i]);
		} 
	}
	cout << ans << '\n';
}
/*
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
*/

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 16032kb

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: 0ms
memory: 15996kb

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: 17172kb

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: 3ms
memory: 17600kb

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: 16564kb

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: 17840kb

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: 14ms
memory: 20120kb

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: 17320kb

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: 17412kb

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: 61ms
memory: 20512kb

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: 0ms
memory: 17324kb

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'