QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311408 | #5073. Elden Ring | Watware | RE | 0ms | 0kb | C++17 | 2.3kb | 2024-01-22 12:33:01 | 2024-01-22 12:33:01 |
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int M = 201000;
using Type = pair<int, int>;
using PQue = priority_queue<Type, vector<Type>, greater<Type>>;
int T, n, m, a, b, l[M], p[M], dis[M];
vector<int> e[M];
inline void solveA() {
if (a != b)
for (int i = 2; i <= n; i++) p[i] = (l[1] - l[i]) / (b - a);
else
for (int i = 2; i <= n; i++) p[i] = l[1] >= l[i] ? INT_MIN : INT_MAX;
PQue q;
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0, q.push({dis[1], 1});
while (!q.empty()) {
auto [d, o] = q.top();
q.pop();
if (d != dis[o]) continue;
for (int i : e[o])
if (dis[i] > dis[o] + 1 && p[i] >= dis[o] + 1) dis[i] = dis[o] + 1, q.push({dis[i], i});
}
printf("%d\n", dis[n] > n ? -1 : dis[n]);
}
inline void solveB() {
for (int i = 2; i <= n; i++) p[i] = max(0, (int) ceil(1.0 * (l[1] - l[i]) / (b - a)));
int _Tmp = 0;
for (int i = 2; i <= n; i++) _Tmp = max(_Tmp, p[i]);
PQue q, s;
memset(dis, 0, sizeof(dis));
q.push({0, 1}), dis[1] = 1;
int cnt = 0;
while (!q.empty()) {
auto [_, o] = q.top();
q.pop();
if (p[o] > cnt) return printf("-1\n"), void();
if (o == n) goto print;
cnt++;
for (int i : e[o])
if (!dis[i]) q.push({p[i], i}), dis[i] = 1;
}
return printf("-1\n"), void();
print:
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0, s.push({dis[1], 1});
while (!s.empty()) {
auto [d, o] = s.top();
s.pop();
if (dis[o] != d) continue;
for (int i : e[o]) {
int t = max(dis[o] + 1, p[i]);
// int t = dis[o] + 1;
if (dis[i] > t) dis[i] = t, s.push({dis[i], i});
}
}
printf("%d\n", dis[n]);
}
inline void solve() {
assert(scanf("%d%d%d%d", &n, &m, &a, &b));
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 1, u, v; i <= m; i++)
assert(scanf("%d%d", &u, &v)), e[u].push_back(v), e[v].push_back(u);
for (int i = 1; i <= n; i++) assert(scanf("%d", l + i));
l[1] -= a;
if (a <= b) solveA();
else solveB();
}
int main() {
freopen("easy.in", "r", stdin);
freopen("easy.out", "w", stdout);
assert(scanf("%d", &T));
while (T--) solve();
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
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