QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735660 | #6306. Chase Game | dsbdsb# | WA | 3ms | 11668kb | C++14 | 1.4kb | 2024-11-11 21:10:19 | 2024-11-11 21:10:19 |
Judging History
answer
#include<bits/stdc++.h>
#define N 200010
#define ll long long
#define pli pair<ll,int>
#define fi first
#define se second
using namespace std;
int n,m,k,dn[N],dk[N];
ll d,dis[N];
vector<int> ve[N];
queue<int> q;
priority_queue<pli> pq;
inline ll solve(ll x){
ll fz=x/d,g=x%d;
ll ans=fz*(d+1)*d/2+g*(2*d-g+1)/2;
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k>>d;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
ve[u].push_back(v);
ve[v].push_back(u);
}
memset(dn,-1,sizeof dn);
q.push(n);
dn[n]=0;
// printf("!!!\n");
while(!q.empty()){
int e=q.front();q.pop();
for(auto i:ve[e]) if(dn[i]==-1){
q.push(i);
dn[i]=dn[e]+1;
}
}
q.push(k);
memset(dk,-1,sizeof dk);
dk[k]=0;
while(!q.empty()){
int e=q.front();q.pop();
for(auto i:ve[e]) if(dk[i]==-1){
q.push(i);
dk[i]=dk[e]+1;
}
}
if(dk[1]>=d+1){
cout<<solve(dn[1]);
return 0;
}
for(auto i:ve[1]){
if(dk[i]<d){
pq.push({dk[i]-d,i});
}
}
ll ans=1e18;
memset(dis,-1,sizeof dis);
dis[1]=0;
while(!pq.empty()){
pli e=pq.top();pq.pop();
if(dis[e.se]!=-1) continue;
dis[e.se]=-e.fi;
if(dk[e.se]==d){
ans=min(ans,solve(dn[e.se]+1)-e.fi);
continue;
}
for(auto i:ve[e.se]){
if(dis[i]!=-1) continue;
pq.push({e.fi+dk[i]-d,i});
}
}
ans=min(ans,solve(dn[1]));
cout<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 11352kb
input:
5 5 3 1 1 2 2 4 4 5 1 3 3 5
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 3ms
memory: 11364kb
input:
13 17 12 3 1 2 2 3 3 4 4 13 5 13 7 8 7 9 7 10 7 11 7 6 12 7 1 8 8 9 9 10 10 11 11 6 6 13
output:
7
result:
ok 1 number(s): "7"
Test #3:
score: 0
Accepted
time: 3ms
memory: 11372kb
input:
10 9 4 1 4 3 1 2 7 6 6 5 8 9 9 10 5 4 8 7 3 2
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 0ms
memory: 11424kb
input:
10 20 9 1 9 5 2 9 4 5 10 5 7 3 1 8 7 1 7 5 3 4 3 1 7 8 3 8 9 3 10 6 9 1 1 6 8 5 6 2 1 10 2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 3ms
memory: 11668kb
input:
10 20 3 1 1 4 6 7 5 4 5 3 2 1 8 1 7 8 2 6 2 4 4 8 9 5 1 10 7 4 5 8 4 10 2 5 6 10 4 6 3 7 1 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 3ms
memory: 11360kb
input:
10 20 4 1 2 7 6 4 2 3 2 4 6 5 8 5 6 7 10 2 3 10 1 8 3 9 3 7 1 7 5 1 6 1 3 4 2 1 5 2 9 2 9 10
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 11312kb
input:
10 20 1 10 10 9 2 5 7 8 7 10 10 8 8 9 5 6 3 1 6 4 7 9 2 3 3 6 2 1 8 6 5 8 7 4 4 3 2 4 4 1 9 6
output:
27
result:
wrong answer 1st numbers differ - expected: '24', found: '27'