QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#296415 | #6306. Chase Game | HJR | WA | 1ms | 3556kb | C++23 | 2.7kb | 2024-01-02 23:32:58 | 2024-01-02 23:32:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
#define int long long
struct node
{
int u,w,ck;
bool operator<(const node&t)const{
return w>t.w;
}
};
void solve(){
int n,m,k,d;
cin>>n>>m>>k>>d;
vector<vector<int>> adj(n+1);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
map<pair<int,int>,int> mp;
queue<int> q;
vector<bool> vis(n+1);
q.push(k);
int cd=0;
while(!q.empty()){
int cn=q.size();
for(int i=0;i<cn;i++){
int cu=q.front();
q.pop();
if(vis[cu])
continue;
vis[cu]=1;
mp[{min(k,cu),max(k,cu)}]=cd;
// kd[cu]=cd;
for(auto x:adj[cu]){
q.push(x);
}
}
cd++;
}
vector<int> res(n+1,1e18);
vector<int> vvvv(n+1);
auto dij=[&](){
priority_queue<node> q;
q.push({1,0,k});
res[1]=0;
while(!q.empty()){
node cur=q.top();
q.pop();
if(vvvv[cur.u])
continue;
vvvv[cur.u]=1;
for(auto x:adj[cur.u]){
int dis=mp[{min(x,cur.ck),max(x,cur.ck)}];
// debug(x);
// debug(cur.ck);
// debug(dis);
if(d-dis<=0){
if(res[cur.u]+d<res[x]){
res[x]=res[cur.u]+d;
q.push({x,res[cur.u]+d,x});
}
for(auto xx:adj[x]){
mp[{min(xx,x),max(xx,x)}]=1;
}
}
else{
if(res[cur.u]+d-dis<res[x]){
res[x]=res[cur.u]+d-dis;
q.push({x,res[cur.u]+d-dis,cur.ck});
}
for(auto xx:adj[x]){
if(mp.count({xx,cur.ck})){
mp[{min(xx,cur.ck),max(xx,cur.ck)}]=min(mp[{min(xx,cur.ck),max(xx,cur.ck)}],dis+1);
}
else
mp[{min(xx,cur.ck),max(xx,cur.ck)}]=dis+1;
}
}
}
}
};
dij();
cout<<res[n]<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t=1;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
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: 0ms
memory: 3556kb
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: 1ms
memory: 3440kb
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: 1ms
memory: 3504kb
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: 1ms
memory: 3552kb
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: 0ms
memory: 3432kb
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: 3548kb
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:
16
result:
wrong answer 1st numbers differ - expected: '24', found: '16'