QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#130398 | #5073. Elden Ring | P3KO | WA | 153ms | 12640kb | C++20 | 2.6kb | 2023-07-23 23:25:19 | 2023-07-23 23:25:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
const ll INF=1e17;
ll n,m,A,B;
vector<ll>to[MAXN];
ll l[MAXN],d[MAXN];
bool vis[MAXN],isreach[MAXN];
ll dis[MAXN];
struct qnode{
ll v,c;
bool operator<(const qnode y)const{
return c>y.c;
}
};
void init(){
for(int i=1;i<=n;i++){
vis[i]=0;
dis[i]=INF;
}
}
void bfs(){
init();
priority_queue<qnode>q;
ll now=0;
isreach[1]=1;
vis[1]=1;
for(auto u:to[1]){q.push({u,d[u]});vis[u]=1;}
while(!q.empty()){
int u=q.top().v;
q.pop();
if(d[u]<=now){
now++;
isreach[u]=1;
for(auto y:to[u]){
if(vis[y])continue;
else {
vis[y]=1;
q.push({y,d[y]});
}
}
}
}
}
void dijkstra(){
init();
priority_queue<qnode>q;
dis[1]=0;
q.push({1,0});
while(!q.empty()){
int v=q.top().v;
q.pop();
if(vis[v])continue;
vis[v]=1;
for(auto y:to[v]){
if(vis[y]||!isreach[y])continue;
if(dis[y]>max(d[y]+1,dis[v]+1)){
dis[y]=max(d[y]+1,dis[v]+1);
q.push({y,dis[y]});
}
}
}
}
void bfs1(){
init();
deque<qnode>q;
q.push_back({1,0});
dis[1]=0;
while(!q.empty()){
int v=q.front().v;
q.pop_front();
if(vis[v])continue;
vis[v]=1;
for(auto y:to[v]){
if(vis[y]||l[y]>=l[1])continue;
if(dis[y]>dis[v]+1){
dis[y]=dis[v]+1;
q.push_back({y,dis[y]});
}
}
}
}
void bfs2(){
init();
deque<qnode>q;
q.push_back({1,0});
dis[1]=0;
while(!q.empty()){
int v=q.front().v;
q.pop_front();
if(vis[v])continue;
vis[v]=1;
for(auto y:to[v]){
if(vis[y]||dis[v]>d[y])continue;
if(dis[y]>dis[v]+1){
dis[y]=dis[v]+1;
q.push_back({y,dis[y]});
}
}
}
}
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld%lld",&n,&m,&A,&B);
for(int i=1;i<=m;i++){
int a,b;scanf("%d%d",&a,&b);
to[a].push_back(b);
to[b].push_back(a);
}
for(int i=1;i<=n;i++)scanf("%lld",&l[i]);
for(int i=2;i<=n;i++)l[i]+=B;
if(A>B){
for(int i=2;i<=n;i++){if(l[i]>=l[1])d[i]=(l[i]-l[1])/(A-B)+1;else d[i]=0;}
bfs();
dijkstra();
if(dis[n]<INF&&isreach[n])printf("%lld\n",dis[n]);
else printf("-1\n");
}else if(A==B){
bfs1();
if(dis[n]<INF&&l[n]<l[1])printf("%lld\n",dis[n]);
else printf("-1\n");
}else{
for(int i=2;i<=n;i++){if(l[1]-l[i]<=0)d[i]=-1;else d[i]=(l[1]-l[i]+B-A-1)/(B-A)-1;}
bfs2();
if(dis[n]<INF)printf("%lld\n",dis[n]);
else printf("-1\n");
}
for(int i=1;i<=n;i++){
to[i].clear();
isreach[i]=0;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 12624kb
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: 153ms
memory: 12640kb
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 -1 -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 559th numbers differ - expected: '-1', found: '6'