QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#556309 | #5073. Elden Ring | Harry27182 | WA | 0ms | 13740kb | C++14 | 1.6kb | 2024-09-10 16:46:05 | 2024-09-10 16:46:05 |
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;
while(!q.empty())
{
int u=q.top().second;q.pop();tot++;
if(vis[u])continue;vis[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]>max(dis[u]+1,t[v])&&tot>=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)cout<<-1<<'\n';
else cout<<dis[n]<<'\n';
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 13740kb
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 -1
result:
wrong answer 2nd numbers differ - expected: '4', found: '-1'