QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#255328 | #5073. Elden Ring | isaunoya | RE | 0ms | 3668kb | C++23 | 2.9kb | 2023-11-18 15:32:55 | 2023-11-18 15:32:56 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
x = x > y ? x : y;
}
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
template <class T> using vc = vector<T>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(time(NULL));
const int inf = 1000000000;
const ll lnf = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
void solve() {
ll n, m, a, b;
cin >> n >> m >> a >> b;
vc<vi> g(n);
rep(i, m) {
int x, y;
cin >> x >> y;
--x;
--y;
g[x].pb(y);
g[y].pb(x);
}
vc<ll> l(n);
rep(i, n) cin >> l[i];
rep(i, 1, n) l[i] += b;
if (a <= b) {
queue<int> q;
q.emplace(0);
vc<ll> w(n);
vc<ll> d(n, -1);
w[0] = l[0];
d[0] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : g[u]) {
if (d[v] == -1 && w[u] > l[v])
d[v] = d[u] + 1, w[v] = w[u] + a - b, q.emplace(v);
}
}
cout << d.back() << "\n";
} else {
pqg<pair<ll, ll>> q;
vi vis(n);
vis[0] = 1;
vi fa(n, -1);
auto add = [&](int u) {
for (auto v : g[u]) {
if (!vis[v]) {
fa[v] = u;
q.emplace(l[v], v);
}
}
};
add(0);
ll pw = l[0];
vi list;
while (!q.empty()) {
auto [val, v] = q.top();
q.pop();
if (val < pw) {
pw += a - b;
vis[v] = 1;
add(v);
list.pb(v);
} else {
break;
}
}
if (!vis.back()) {
cout << "-1\n";
return;
}
vi key;
int x = n - 1;
while (~x) {
key.pb(x);
x = fa[x];
}
key.pop_back();
reverse(all(key));
// debug(key);
pw = l[0];
rep(i, n) vis[i] = 0;
int j = 0;
for (auto x : key) {
while (pw <= l[x]) {
if (!vis[list[j]]) {
vis[list[j]] = 1;
pw += a - b;
}
j += 1;
}
vis[x] = 1;
pw += a - b;
}
cout << accumulate(all(vis), 0) << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3668kb
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
Runtime Error
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...