QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#362330 | #6306. Chase Game | Zxc200611 | WA | 1ms | 8604kb | C++14 | 1.9kb | 2024-03-23 15:02:08 | 2024-03-23 15:02:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x7f7f7f7f7f7f7f7f;
int n,m,p,d;
vector<int> t[110000];
int disN[110000],disP[110000];
int dmg1[110000];
int calcDamage(int dis)
{
dis+=1;
int c=dis/d,r=dis%d;
return c*(d*(d+1)/2)+r*(d+d-r+1)/2;
}
void getDistance(int s,int *dis,bool ty)
{
// cout<<"getDistance s="<<s<<" ty="<<ty<<endl;
struct Item
{
int u,d;
bool operator<(Item b) const
{
return d>b.d;
}
};
static priority_queue<Item> q={};
static bool vis[210000];
for(int i=1;i<=n;i++)
dis[i]=inf,vis[i]=0;
dis[s]=0,q.push((Item){s,dis[s]});
while(!q.empty())
{
int u=q.top().u;
q.pop();
if(vis[u])
continue;
vis[u]=1;
// cout<<"u="<<u<<" dis="<<dis[u]<<endl;
for(int i=0;i<t[u].size();i++)
{
int v=t[u][i];
if(ty==1&&disP[v]>=d)
continue;
int ndis=dis[u]+(ty==0?1:d-disP[v]);
// cout<<"v="<<v<<" ndis="<<ndis<<endl;
if(!vis[v]&&ndis<dis[v])
dis[v]=ndis,q.push((Item){v,dis[v]});
}
}
}
signed main()
{
cin>>n>>m>>p>>d;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
t[u].push_back(v);
t[v].push_back(u);
}
getDistance(n,disN,0);
getDistance(p,disP,0);
getDistance(1,dmg1,1);
// cout<<"disN :";
// for(int i=1;i<=n;i++)
// cout<<" "<<disN[i];
// cout<<endl;
// cout<<"disP :";
// for(int i=1;i<=n;i++)
// cout<<" "<<disP[i];
// cout<<endl;
// cout<<"dmg1 :";
// for(int i=1;i<=n;i++)
// cout<<" "<<dmg1[i];
// cout<<endl;
int ans=calcDamage(disN[1]-1);
if(disP[1]<=d)
{
for(int u=1;u<=n;u++)
{
for(int v:t[u])
{
if(disP[v]==disP[u]+1&&disP[v]==d)
{
ans=min<int>(ans,dmg1[u]+calcDamage(disN[v]));
}
}
}
}
cout<<ans<<endl;
}
/*
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
1
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7508kb
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: 8120kb
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: 8604kb
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: 7328kb
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: 6924kb
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: 8596kb
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: 7848kb
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:
27
result:
wrong answer 1st numbers differ - expected: '24', found: '27'