QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#745932 | #6306. Chase Game | dezex# | WA | 1ms | 6652kb | C++20 | 2.2kb | 2024-11-14 12:29:06 | 2024-11-14 12:29:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
vector<int> nb[N];
ll ds[N],dk[N],dt[N];
int vis[N];
int n,m,k;ll rg;
bool flag[N];
void bfs(int s, ll *dis)
{
//dis all -1
queue<int> q;
q.push(s);dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(auto v:nb[u])
{
if(dis[v] != -1)
continue;
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
void dij(int s,ll *d)
{
memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
d[s]=0;
priority_queue<pair<ll,int>> q;
q.push(make_pair(0,1));
vis[s]=1;
while(!q.empty())
{
int u=q.top().second;q.pop();
// if(u==n)
// break;
if(rg - dk[u] <= 0 && u!=s)
{
flag[u]=true;
continue;
};
for(auto v:nb[u])
{
if(vis[v])
continue;
d[v]=d[u]+max(0ll,rg-dk[v]);
// printf("%d->%d\n",u,v);
vis[v]=1;
q.push(make_pair(-d[v],v));
};
}
}
inline ll calc(ll l)
{
ll ans = (l/rg) * ((rg+1)*rg/2);
ll k = l%rg;
ans += (rg+rg+k-1) * k / 2;
return ans;
}
int main()
{
scanf("%d %d %d %lld",&n,&m,&k,&rg);
for(int i=1;i<=m;i++)
{
int u,v;scanf("%d %d",&u,&v);
nb[u].push_back(v);
nb[v].push_back(u);
};
memset(dk,-1,sizeof(dk));
memset(dt,-1,sizeof(dt));
bfs(k, dk);
bfs(n, dt);
dij(1, ds);
// for(int i=1;i<=n;i++)
// printf("dk[%d]=%lld\n",i,dk[i]);
// printf("\n");
// for(int i=1;i<=n;i++)
// printf("dt[%d]=%lld\n",i,dt[i]);
// printf("\n");
// for(int i=1;i<=n;i++)
// printf("ds[%d]=%lld\n",i,ds[i]);
// printf("\n");
// printf("flag:\n");
ll ans=-1;
for(int u=1;u<=n;u++)
if(flag[u])
{
// printf("%d ",u);
ll t = ds[u] + calc(dt[u]+1);
ans = ans==-1?t:min(t,ans);
};
// printf("\n");
printf("%lld\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5884kb
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: 5704kb
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: 6068kb
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: 5744kb
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: 6652kb
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: 5952kb
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: 1ms
memory: 5988kb
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:
-1
result:
wrong answer 1st numbers differ - expected: '24', found: '-1'