QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116670 | #6523. Escape Plan | ITMO_pengzoo# | WA | 937ms | 41692kb | C++20 | 5.1kb | 2023-06-29 18:55:22 | 2023-06-29 18:55:24 |
Judging History
answer
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <stdio.h>
#include <bits/stdc++.h>
#ifdef PERVEEVM_LOCAL
#define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
#define debug(x) 238
#endif
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"
using ll = long long;
using ld = long double;
#ifdef PERVEEVM_LOCAL
std::mt19937 rnd(238);
#else
std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
out << "(" << p.first << ", " << p.second << ")";
return out;
}
template<size_t index, typename T>
std::ostream& print_tuple(std::ostream& out, const T& t) {
if constexpr (index == std::tuple_size<T>::value) {
out << ")";
return out;
} else {
if (index > 0) {
out << ", ";
} else {
out << "(";
}
out << std::get<index>(t);
return print_tuple<index + 1, T>(out, t);
}
}
template<typename ...T>
std::ostream& operator<<(std::ostream& out, const std::tuple<T...>& t) {
return print_tuple<0, std::tuple<T...>>(out, t);
}
template<typename Container, typename = decltype(std::begin(std::declval<Container>()))>
typename std::enable_if<!std::is_same<Container, std::string>::value, std::ostream&>::type
operator<<(std::ostream& out, const Container& container) {
out << "{";
for (auto it = container.begin(); it != container.end(); ++it) {
if (it != container.begin()) {
out << ", ";
}
out << *it;
}
out << "}";
return out;
}
template<typename T>
bool smin(T& a, const T& b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool smax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 100100;
std::vector<std::pair<int, int>> g[N];
int monsters[N];
std::priority_queue<ll> heaps[N];
ll dist[N];
class Comparator {
public:
bool operator()(int i1, int i2) const {
ll val1 = heaps[i1].top();
ll val2 = heaps[i2].top();
return val1 < val2 || (val1 == val2 && i1 < i2);
}
};
void solve() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; ++i) {
g[i].clear();
while (!heaps[i].empty()) {
heaps[i].pop();
}
dist[i] = LINF;
}
std::vector<int> exits(k);
for (int i = 0; i < k; ++i) {
scanf("%d", &exits[i]);
--exits[i];
}
for (int i = 0; i < n; ++i) {
scanf("%d", &monsters[i]);
}
for (int i = 0; i < m; ++i) {
int from, to, cost;
scanf("%d%d%d", &from, &to, &cost);
g[from - 1].emplace_back(to - 1, cost);
g[to - 1].emplace_back(from - 1, cost);
}
for (auto i : exits) {
monsters[i] = 0;
}
for (int i = 0; i < n; ++i) {
smin(monsters[i], (int)g[i].size());
for (int j = 0; j < monsters[i] + 1; ++j) {
heaps[i].push(LINF);
}
}
for (auto i : exits) {
while (!heaps[i].empty()) {
heaps[i].pop();
}
heaps[i].push(0);
}
std::set<int, Comparator> setik;
auto update = [&](int v, ll d) {
// std::cout << "Updating " << v << ' ' << d << std::endl;
if (heaps[v].top() <= d) {
return;
}
bool fl = setik.find(v) != setik.end();
if (fl) {
setik.erase(v);
}
heaps[v].pop();
heaps[v].push(d);
if (fl) {
setik.insert(v);
}
};
for (int i = 0; i < k; ++i) {
int cur = exits[i];
update(cur, 0);
dist[cur] = 0;
setik.insert(cur);
}
while (!setik.empty()) {
int v = *setik.begin();
setik.erase(setik.begin());
// debug(v);
// debug(dist[v]);
// debug(heaps[v].size());
// debug(heaps[v].top());
assert(dist[v] != LINF);
assert(heaps[v].top() != LINF);
assert(heaps[v].top() >= dist[v]);
for (auto[to, cost] : g[v]) {
if (dist[v] + cost < dist[to]) {
update(to, dist[v] + cost);
if (heaps[to].top() != LINF) {
setik.insert(to);
dist[to] = dist[v] + cost;
}
}
}
}
if (dist[0] == LINF) {
printf("-1\n");
} else {
printf("%lld\n", dist[0]);
}
}
void run() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
}
int main(void) {
// freopen(NAME".in", "r", stdin);
// freopen(NAME".out", "w", stdout);
#ifdef PERVEEVM_LOCAL
auto start = std::chrono::high_resolution_clock::now();
#endif
run();
#ifdef PERVEEVM_LOCAL
auto end = std::chrono::high_resolution_clock::now();
std::cerr << "Execution time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms" << std::endl;
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9528kb
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
Wrong Answer
time: 937ms
memory: 41692kb
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...
output:
3376 429 1339 2010 1432 1445 331 3207 670 923 1083 837 360 1114 741 2893 223 1138 1353 658 3186 1751 425 1694 2247 10728 842 2322 436 628 1788 490 651 -1 765 6265 507 1445 613 678 402 3769 12802 4341 4320 1953 -1 510 729 2792 -1 913 773 1907 990 557 2446 270 1251 485 1384 954 1472 1295 516 2882 938 ...
result:
wrong answer 1st numbers differ - expected: '5109', found: '3376'