QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#556313 | #5073. Elden Ring | Harry27182 | WA | 126ms | 14068kb | C++14 | 1.6kb | 2024-09-10 16:49:33 | 2024-09-10 16:49:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct edge{int v,nxt;}e[2000005];
int T,n,m,A,B,h[500005],w[500005],t[500005],cnt,dis[500005],vis[500005],u,v;
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>T;
while(T--)
{
cin>>n>>m>>A>>B;
for(int i=1;i<=n;i++)h[i]=0;cnt=0;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=2;i<=n;i++)w[i]+=B;
if(A<=B)
{
for(int i=2;i<=n;i++)
{
if(A==B)t[i]=(w[i]<w[1]?0x3f3f3f3f:0);
else t[i]=max(0,(w[1]-w[i]-1)/(B-A)+1);
}
queue<int>q;q.push(1);
for(int i=1;i<=n;i++)dis[i]=-1;dis[1]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]==-1&&dis[u]+1<=t[v])
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
cout<<dis[n]<<'\n';
}
else
{
for(int i=2;i<=n;i++)t[i]=(w[i]<w[1]?1:(w[i]-w[1])/(A-B)+2);
priority_queue<pair<int,int> >q;q.push(make_pair(0,1));
for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f,vis[i]=0;dis[1]=0;
int tot=0,flag=0;
while(!q.empty())
{
int u=q.top().second;q.pop();
if(vis[u])continue;vis[u]=1;
if(tot<dis[u]){flag=1;break;}
tot++;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]>max(dis[u]+1,t[v]))
{
dis[v]=max(dis[u]+1,t[v]);
q.push(make_pair(-dis[v],v));
}
}
}
if(dis[n]==0x3f3f3f3f||flag==1)cout<<-1<<'\n';
else cout<<dis[n]<<'\n';
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 13992kb
input:
2 5 4 5 8 1 2 1 3 1 4 4 5 15 1 1 1 1 5 4 10 5 1 2 1 3 1 4 4 5 10 4 4 4 19
output:
2 4
result:
ok 2 number(s): "2 4"
Test #2:
score: -100
Wrong Answer
time: 126ms
memory: 14068kb
input:
100000 6 10 107812 105568 6 5 3 6 4 6 4 2 5 1 5 6 4 5 1 3 1 2 2 5 124065 140875 29890 80077 116532 35394 9 10 82107 88302 1 2 2 3 5 3 5 1 1 4 9 6 3 5 8 2 5 6 7 5 22670 3735 33660 92823 139960 89319 83335 158330 117349 6 10 181257 173221 5 3 3 4 3 1 5 1 2 1 3 6 3 1 6 2 3 6 4 3 76902 46253 123092 2661...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
wrong answer 4th numbers differ - expected: '1', found: '-1'