QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274404 | #5073. Elden Ring | LLLLL | WA | 156ms | 10424kb | C++14 | 2.0kb | 2023-12-03 15:19:06 | 2023-12-03 15:19:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,m,A,B,l[N];
#define ll long long
int dis[N],c[N],vis[N];
vector<int>e[N];
struct nod{
int id,val;
bool operator<(const nod&x)const{
return val>x.val;
}
};
priority_queue<nod>q;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&m,&A,&B);
memset(dis,-1,sizeof(int)*(n+1));
for(int i=1;i<=n;i++)e[i].clear();
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)scanf("%d",&l[i]);
for(int i=2;i<=n;i++)
{
l[i]+=B;
if(A==B)c[i]=(l[i]<l[1])?0:1e9;
else if(A<B)c[i]=(l[1]-l[i])/(B-A);
else
{
if(l[i]<l[1])c[i]=0;
else c[i]=(l[i]-l[1]-1)/(A-B)+1;
}
// printf("%d ",c[i]);
}
// puts("");
if(A<=B)//最晚ci打
{
q.push((nod){1,0});
dis[1]=0;
while(!q.empty())
{
nod now=q.top();
q.pop();
// printf("now::%d %d\n",now.id,now.val);
if(dis[now.id]!=now.val)continue;
for(int to:e[now.id])
{
if(dis[now.id]<=c[to]&&(dis[to]>dis[now.id]+1||dis[to]==-1))
{
dis[to]=dis[now.id]+1;
q.push((nod){to,dis[to]});
}
}
}
printf("%d\n",dis[n]);
}
else
{
memset(vis,0,sizeof(int)*(n+1));
q.push((nod){1,0});
int Nl=l[1];
while(!q.empty())
{
nod now=q.top();
q.pop();
if(now.val>Nl)continue;
vis[now.id]=1;
Nl+=A-B;
for(int to:e[now.id])
if(!vis[to])q.push((nod){to,l[to]});
}
for(int i=1;i<=n;i++)
if(vis[i])dis[i]=1e9;
q.push((nod){1,0});
dis[1]=0;
while(!q.empty())
{
nod now=q.top();
q.pop();
if(dis[now.id]!=now.val)continue;
for(int to:e[now.id])
{
if(vis[to]&&dis[to]>max(dis[now.id]+1,c[to]))
{
dis[to]=max(dis[now.id]+1,c[to]);
q.push((nod){to,dis[to]});
}
}
}
printf("%d\n",dis[n]==-1?-1:(dis[n]+1));
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 10424kb
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: 156ms
memory: 9696kb
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 2 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -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 4 -1 2 -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 -...
result:
wrong answer 4th numbers differ - expected: '1', found: '2'