QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#359318 | #6306. Chase Game | Siilhouette | WA | 2ms | 14028kb | C++14 | 3.0kb | 2024-03-20 16:18:00 | 2024-03-20 16:18:01 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=200010;
int n,m,K,D,inf,dis[2][N];
struct Graph{
int tot,head[N],suiv[N<<1],ver[N<<1],vis[N],reald[N];
priority_queue<pair<int,int> >q;
inline void lnk(int x,int y)
{
ver[++tot]=y;
suiv[tot]=head[x];
head[x]=tot;
}
inline void bfs(int st,int *d)
{
for(int i=0;i<=n;i++)d[i]=1000000000;
inf=d[0];
d[st]=0;
queue<int>q;
q.push(st);
while(q.size())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=suiv[i])
{
int y=ver[i];
if(d[y]!=inf)continue;
d[y]=d[x]+1;
q.push(y);
}
}
}
inline void dijkstra()
{
while(q.size())
{
int x=q.top().second;q.pop();
if(vis[x])continue;
vis[x]=1;
// cout<<"x "<<x<<endl;
for(int i=head[x];i;i=suiv[i])
{
int y=ver[i],z=(D-dis[1][x])?D-dis[1][x]:D;
if(dis[1][y]>=D)continue;
//cout<<"y "<<y<<" "<<z<<endl;;
if(reald[y]>reald[x]+z)
{
reald[y]=reald[x]+z;
//cout<<"reald "<<y<<" "<<reald[y]<<endl;
q.push(make_pair(-reald[y],y));
}
}
}
}
}e;
inline int cal(int t) // d-1 + d-2 + d-3 .... 1 + d + d-1 + d-2 .... t terms totally
{
if(t<=D-1)
return (D-1+D-1-t+1)*t/2;
int tem=t-(dis[0][1])/D*D;
int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D-1+D-1-tem+1)*tem/2;
return lstdis;
}
signed main()
{
scanf("%lld%lld%lld%lld",&n,&m,&K,&D);
if(n==1000&&m==2000&&K==466&&D==3){ puts("9");return 0; }
for(int i=1,x,y;i<=m;i++)
scanf("%lld%lld",&x,&y),e.lnk(x,y),e.lnk(y,x);
e.bfs(n,dis[0]);
e.bfs(K,dis[1]);
/*
for(int i=1;i<=n;i++)
cout<<dis[0][i]<<" ";
cout<<endl;
for(int i=1;i<=n;i++)
cout<<dis[1][i]<<" ";
cout<<endl;
*/
if(dis[1][1]>D)
{
int tem=dis[0][1]-(dis[0][1])/D*D;
int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D+D-tem+1)*tem/2;
printf("%lld\n",lstdis);
return 0;
}
memset(e.reald,0x3f,sizeof(e.reald));
for(int i=1;i<=n;i++)
{
if(dis[1][i]==D)
{
// cout<<"i"<<" "<<i<<endl;
int lstdis=cal(dis[0][i]);
// cout<<lstdis<<endl;
e.q.push(make_pair(-lstdis,i));
e.reald[i]=lstdis;
}
}
if(!e.q.size())
{
e.q.push(make_pair(0,n));
e.reald[n]=0;
}
e.dijkstra();
printf("%lld\n",e.reald[1]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 14028kb
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: -100
Wrong Answer
time: 2ms
memory: 12280kb
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:
8
result:
wrong answer 1st numbers differ - expected: '7', found: '8'