QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#332242 | #6306. Chase Game | automac# | WA | 2ms | 9904kb | C++20 | 3.8kb | 2024-02-19 12:29:18 | 2024-02-19 12:29:19 |
Judging History
answer
#include <bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r) for(int i = (int)l; i <= (int)r; ++i)
#define all(x) x.begin(), x.end()
#define el '\n'
#define d(x) cerr << #x << ' ' << x << el
#define sz(a) (int) a.size()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int,int> ii;
typedef tuple<ll,int,int> iii;
const int nax = 2e5;
// const int nax = 2e3;
vi g[nax];
ll dist[3][nax];
int visited[3][nax];
const ll inf = 1e17;
void solve(){
int n,m,k,d;
cin>>n>>m>>k>>d;
--k;
forn(i,m){
int u,v;
cin>>u>>v;
--u,--v;
g[u].pb(v), g[v].pb(u);
}
queue<ii> q;
q.push({n-1, d-1});
dist[0][n-1] = 0;
visited[0][n-1]= 1;
while(!q.empty()){
int siz = sz(q);
while(siz--){
auto [u, mod]= q.front();
q.pop();
ll curDist = dist[0][u];
for(int v : g[u]){
if(!visited[0][v])
{
visited[0][v] = 1;
int newMod = (mod+1) % d;
if(!newMod) newMod=d;
dist[0][v] = curDist + newMod;
q.push({v, newMod});
}
}
}
}
queue<int> q1;
q1.push(k);
visited[1][k] = 1;
dist[1][k] = 0;
while(!q1.empty()){
int siz = sz(q1);
while(siz--){
auto u = q1.front();
q1.pop();
ll curDist = dist[1][u];
for(int v : g[u]){
if(!visited[1][v])
{
visited[1][v] = 1;
dist[1][v] = curDist + 1;
q1.push(v);
}
}
}
}
q1.push(0);
visited[2][0] = 1;
dist[2][0] = 0;
ll ans = inf;
while(!q1.empty()){
int siz = sz(q1);
while(siz--){
auto u = q1.front();
q1.pop();
ll curDist = dist[2][u];
for(int v : g[u]){
if(!visited[2][v])
{
visited[2][v] = 1;
bool joined = dist[1][v] >= d;//dist al K
if(joined){
ans = min(ans, curDist + dist[0][u]);
}else{
dist[2][v] = curDist + d - dist[1][v];
q1.push(v);
}
}
}
}
}
cout<<ans<<el;
// priority_queue<iii, vector<iii>, greater<iii>> qq;
// qq.push({0,0,1});
// vector<vector<ll>> curDist(2, vector<ll>(n, inf));
// curDist[1][0] = 0;
// while(!qq.empty()){
// int siz = sz(qq);
// while(siz--){
// auto [distU, u, same] = qq.top();
// // d(distU), d(u), d(same);
// qq.pop();
// if(distU > curDist[same][u]) continue;
// for(int v : g[u]){
// // d(v);
// bool newSame = (dist[0][v] < d) && same;
// // d(newSame);
// ll cost = d;
// if(newSame) cost = d - dist[0][v];
// if(distU + cost < curDist[newSame][v]){
// curDist[newSame][v] = distU + cost;
// qq.push({curDist[newSame][v], v, newSame});
// }
// }
// }
// }
// ll ans = min(curDist[0][n-1], curDist[1][n-1]);
// cout<<ans<<el;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tt = 1;
// cin>>tt;
while(tt--){
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 7720kb
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: 2ms
memory: 9904kb
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: 0ms
memory: 7644kb
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: 2ms
memory: 9768kb
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: 7704kb
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: 7576kb
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: 2ms
memory: 7596kb
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:
100000000000000000
result:
wrong answer 1st numbers differ - expected: '24', found: '100000000000000000'