QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311426 | #5073. Elden Ring | Ryan123 | WA | 0ms | 10180kb | C++14 | 2.9kb | 2024-01-22 12:51:41 | 2024-01-22 12:51:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
vector<int> e[N];
int w[N], mn[N];
int d[N];
bool vis[N];
int L;
int n, m, A, B;
void dij1(){
memset(d, 63, sizeof(d));
memset(vis, 0, sizeof(vis));
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
d[1] = 0;
q.push({0, 1});
while(!q.empty()){
int x = q.top().second;
q.pop();
if(vis[x])continue;
// if(w[x] + 1ll * d[x] * (B - A) >= L)continue;
vis[x] = 1;
for(int u : e[x]){
if(d[u] > d[x] + 1 && w[u] + 1ll * d[x] * (B - A) < L){
d[u] = d[x] + 1;
q.push({d[u], u});
}
}
}
}
bool check(){
memset(vis, 0, sizeof(vis));
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int cnt = 0;
vis[1] = 1;
for(int u : e[1]){
// printf("%d\n", u);
if(!vis[u]){
q.push({w[u], u});
vis[u] = 1;
}
}
while(!q.empty()){
int x = q.top().second;
q.pop();
if(w[x] >= L + 1ll * (A - B) * cnt)return 0;
if(x == n)return 1;
cnt ++;
for(int u : e[x]){
if(!vis[u]){
printf("%d\n", u);
q.push({w[u], u});
vis[u] = 1;
}
}
}
return 0;
}
void dij2(){
memset(d, 63, sizeof(d));
memset(vis, 0, sizeof(vis));
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
d[1] = 0;
q.push({0, 1});
while(!q.empty()){
int x = q.top().second;
q.pop();
if(vis[x])continue;
vis[x] = 1;
for(int u : e[x]){
if(d[u] > max(d[x] + 1, mn[u] + 1)){
d[u] = max(d[x] + 1, mn[u] + 1);
q.push({d[u], u});
}
}
}
}
void solve(){
scanf("%d%d%d%d", &n, &m, &A, &B);
for(int i = 1; i <= n; i ++)e[i].clear();
for(int i = 1; i <= m; i ++){
int a, b;
scanf("%d%d", &a, &b);
e[a].push_back(b);
e[b].push_back(a);
}
scanf("%d", &L);
for(int i = 2; i <= n; i ++){
scanf("%d", &w[i]);
w[i] += B;
}
if(B >= A){
dij1();
if(d[n] >= 1e8)puts("-1");
else printf("%d\n", d[n]);
}
else {
if(!check()){
puts("-1");
return ;
}
for(int i = 2; i <= n; i ++){
if(w[i] < L)mn[i] = 0;
else {
int t = w[i] - L + 1;
mn[i] = t / (A - B);
if(t % (A - B))mn[i] ++;
}
}
dij2();
printf("%d\n", d[n]);
}
}
int main(){
int T;
scanf("%d", &T);
while(T --){
solve();
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 10180kb
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 5 4
result:
wrong answer 2nd numbers differ - expected: '4', found: '5'