QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#556326 | #5073. Elden Ring | Harry27182 | WA | 109ms | 13844kb | C++14 | 1.7kb | 2024-09-10 16:55:56 | 2024-09-10 16:55:56 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
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;}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>T;
for(int _=1;_<=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];
if(_==16)cout<<n<<'\n';
if(_>=3&&_!=16)continue;
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(0ll,(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();
if(vis[u])continue;vis[u]=1;
if(tot<dis[u])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)cout<<-1<<'\n';
else cout<<dis[n]<<'\n';
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 13844kb
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: 109ms
memory: 13804kb
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 8 22
result:
wrong answer 3rd numbers differ - expected: '-1', found: '8'