QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#420897 | #6523. Escape Plan | shepherd | RE | 0ms | 3612kb | C++20 | 1.9kb | 2024-05-25 03:01:17 | 2024-05-25 03:01:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static constexpr const ll inf = 1e15;
int main() {
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
vector<bool> is_exit(n);
for (int i = 0; i < k; i++) {
int e;
cin >> e;
is_exit[--e] = true;
}
vector<int> d(n);
for (int i = 0; i < n; i++) {
cin >> d[i];
}
vector<vector<pair<int, ll>>> graph(n);
for (int i = 0; i < m; i++) {
int x, y;
ll w;
cin >> x >> y >> w;
graph[--x].emplace_back(--y, w);
graph[y].emplace_back(x, w);
}
vector<ll> ret(n, inf);
vector<bool> marked(n, false);
vector<multiset<ll>> dd(n);
auto cmp = [&](int x, int y) {
auto dx = *prev(end(dd[x]));
auto dy = *prev(end(dd[y]));
if (dx != dy) return dx < dy;
return x < y;
};
set<int, decltype(cmp)> q(cmp);
for (int i = 0; i < n; i++) {
if (is_exit[i]) {
dd[i].insert(0);
q.insert(i);
d[i] = 0;
}
}
while (!q.empty()) {
auto curr = *q.begin();
q.erase(q.begin());
marked[curr] = true;
ret[curr] = *prev(end(dd[curr]));
for (const auto& [neighbor, weight] : graph[curr]) {
if (marked[neighbor]) continue;
if (int(dd[neighbor].size()) > d[neighbor]) {
q.erase(neighbor);
}
if (!dd[neighbor].empty())
assert(*prev(end(dd[neighbor])) <= ret[curr] + weight);
dd[neighbor].insert(ret[curr] + weight);
while (int(dd[neighbor].size()) > d[neighbor] + 1) {
dd[neighbor].erase(prev(end(dd[neighbor])));
}
if (int(dd[neighbor].size()) > d[neighbor]) {
q.insert(neighbor);
}
}
}
if (ret[0] >= inf)
cout << -1 << '\n';
else
cout << ret[0] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
input:
2 3 4 1 3 1 1 1 1 2 1 1 2 2 2 3 1 2 3 2 3 2 2 2 3 2 0 0 1 2 1 1 3 1
output:
4 -1
result:
ok 2 number(s): "4 -1"
Test #2:
score: -100
Runtime Error
input:
100 100 1808 2 94 47 3 3 0 2 4 3 3 4 0 0 2 2 2 3 2 4 0 2 3 4 4 2 0 3 4 3 1 0 2 1 2 2 0 3 4 4 4 1 2 2 3 1 0 0 3 1 4 2 1 3 3 4 3 0 4 1 0 3 2 1 4 4 1 3 2 3 3 3 3 1 0 3 0 4 3 1 0 4 0 4 4 1 2 0 0 4 1 3 3 3 0 2 2 1 1 2 3 4 1 2 72 29 1138 59 78 2398 95 5 1610 32 46 4176 36 99 8143 100 69 413 61 58 1595 9 9...