QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#332286 | #6306. Chase Game | automac | RE | 1ms | 3824kb | C++20 | 3.0kb | 2024-02-19 13:17:42 | 2024-02-19 13:17:42 |
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});
dist[0][n-1] = d;
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) % 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);
}
}
}
}
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
pq.push({0,0});
vector<ll> curDist(n, inf);
curDist[0] = 0;
ll ans = inf;
while(!pq.empty()){
int siz = sz(pq);
while(siz--){
auto [distU, u] = pq.top();
// d(distU), d(u), d(same);
pq.pop();
if(distU > curDist[u]) continue;
for(int v : g[u]){
bool joined = dist[1][v] >= d;//dist al K
if(joined){
ans = min(ans, distU + dist[0][v]);
}else{
if(curDist[v] > distU + d - dist[1][v]){
curDist[v] = distU + d - dist[1][v];
pq.push({curDist[v], v});
}
}
}
}
}
assert(ans != inf);
cout<<ans<<el;
// 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: 1ms
memory: 3596kb
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: 1ms
memory: 3636kb
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: 3636kb
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: 3632kb
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: 3764kb
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: 1ms
memory: 3824kb
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
Runtime Error
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