QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #274456 | #5073. Elden Ring | MaMengQi2 | WA | 152ms | 10368kb | C++14 | 2.0kb | 2023-12-03 15:42:04 | 2023-12-03 15:42: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,0x7f,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])?1e9:-1;
else if(A<B)c[i]=l[i]<l[1]?(l[1]-l[i]-1)/(B-A):-1;
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]=dis[now.id]+1;
q.push((nod){to,dis[to]});
}
}
}
printf("%d\n",dis[n]>=5e8?-1:dis[n]);
}
else
{
memset(vis,0,sizeof(int)*(n+1));
q.push((nod){1,0});
vis[1]=2;
int Nl=l[1];
while(!q.empty())
{
nod now=q.top();
q.pop();
if(now.val>=Nl)continue;
vis[now.id]=2;
Nl+=A-B;
for(int to:e[now.id])
if(!vis[to])q.push((nod){to,l[to]}),vis[to]=1;
}
q.push((nod){1,0});
dis[1]=0;
if(vis[n]==2)
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]==2&&dis[to]>max(dis[now.id],c[to])+1)
{
dis[to]=max(dis[now.id],c[to])+1;
q.push((nod){to,dis[to]});
}
}
printf("%d\n",dis[n]>=5e8?-1:(dis[n]));
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10368kb
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: 152ms
memory: 10284kb
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 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 3 -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 2 -1 -1 -1 -1 -1 -...
result:
wrong answer 56th numbers differ - expected: '-1', found: '3'