QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#368525 | #6523. Escape Plan | kabuu | RE | 1ms | 3548kb | C++20 | 2.5kb | 2024-03-27 11:01:47 | 2024-03-27 11:01:48 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define debug cerr << 6666 << endl;
#pragma GCC optimize(2)
using namespace std;
const ll mod = 998244353;
const ll N = 1e6 + 100;
const ll inf = 1e18;
void solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> e(k + 1);
for (int i = 1; i <= k; i++)
cin >> e[i];
vector<int> d(n + 1);
for (int i = 1; i <= n; i++)
cin >> d[i];
vector<vector<array<int, 3>>> g(n + 1);
vector<vector<ll>> dis(n + 1);
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({ v, w, dis[u].size() + 1 });
g[v].push_back({ u, w, dis[v].size() + 1 });
dis[u].push_back(inf);
dis[v].push_back(inf);
}
for (int i = 1; i <= n; i++)
dis[i].push_back(1e18);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
for (int i = 1; i <= k; i++) {
q.push({ 0, e[i] });
for (int j = 1; j < dis[e[i]].size(); j++)
dis[e[i]][j] = 0;
}
auto monst = d;
// cerr << 666;
vector<bool> vis(n + 1);
while (q.size()) {
auto [far, u] = q.top();
q.pop();
if (vis[u])
continue;
vis[u] = 1;
for (auto [v, w, id] : g[u]) {
// if (dis[v][cur] > far + 1ll * u) {
if (dis[v][id] == inf) {
monst[v]--;
}
dis[v][id] = min(dis[v][id], far + 1ll * w);
// cerr << v << " " << far + w << '\n';
if (monst[v] <= 0) {
// cerr << 666;
auto tmp = dis[v];
sort(tmp.begin() + 1, tmp.end());
// for (auto x : tmp)
// cerr << x << " ";
// cerr << "\n";
if (tmp[d[v] + 1] != inf && !vis[v]) {
// cerr << v << " " << tmp[d[v] + 1] << " \n";
q.push({ tmp[d[v] + 1], v });
}
}
// }
}
}
auto tmp = dis[1];
sort(tmp.begin() + 1, tmp.end());
// for (auto x : tmp)
// cerr << x << " ";
if (d[1] + 1 == dis[1].size() || tmp[d[1] + 1] == inf) {
cout << -1 << '\n';
} else {
cout << tmp[d[1] + 1] << '\n';
}
}
/*
*/
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
int T_T = 1;
std::cin >> T_T;
while (T_T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
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...