QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311419 | #5073. Elden Ring | Ryan123 | WA | 146ms | 10824kb | C++14 | 3.3kb | 2024-01-22 12:43:05 | 2024-01-22 12:43:06 |
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, (n + 2) * sizeof(int));
memset(vis, 0, (n + 2) * sizeof(bool));
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, (n + 2) * sizeof(bool));
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]){
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]){
q.push({w[u], u});
vis[u] = 1;
}
}
}
return 0;
}
void dij2(){
memset(d, 63, (n + 2) * sizeof(int));
memset(vis, 0, (n + 2) * sizeof(bool));
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});
}
}
}
}
int T;
int idx = 0;
void solve(){
idx ++;
scanf("%d%d%d%d", &n, &m, &A, &B);
for(int i = 1; i <= n; i ++)e[i].clear();
if(idx == 559)printf("%d %d %d %d\n", n, m, A, B);
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);
if(idx == 559)printf("%d %d\n", a, b);
}
scanf("%d", &L);
if(idx == 559)printf("%d ", L);
for(int i = 2; i <= n; i ++){
scanf("%d", &w[i]);
if(idx == 559)printf("%d ", w[i]);
w[i] += B;
}
if(B >= A){
dij1();
if(T != 100000){
if(d[n] >= 1e8)puts("-1");
else printf("%d\n", d[n]);
}
}
else {
// printf("%d\n", w[110000000]);
if(!check()){
if(T != 100000)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();
if(T != 100000)printf("%d\n", d[n]);
}
}
int main(){
// freopen("easy.in", "r", stdin);
// freopen("easy.out", "w", stdout);
scanf("%d", &T);
for(int t = 1; t <= T; t ++){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9916kb
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: 146ms
memory: 10824kb
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:
5 10 8746 5535 1 3 2 1 2 3 5 4 5 1 2 1 4 1 1 4 1 3 4 1 186243 182643 22371 46227 194225
result:
wrong answer 1st numbers differ - expected: '-1', found: '5'