QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#834183 | #2647. Environment-Friendly Travel | what_a_name | AC ✓ | 61ms | 20512kb | C++14 | 3.0kb | 2024-12-27 12:54:24 | 2024-12-27 12:54:25 |
Judging History
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
*/
Details
Tip: Click on the bar to expand more detailed information
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'