QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#109313 | #6523. Escape Plan | xuxubaobao | TL | 8ms | 58128kb | C++17 | 1.7kb | 2023-05-28 12:57:21 | 2023-05-28 12:57:25 |
Judging History
answer
// Super Idol的笑容
// 都没你的甜
// 八月正午的阳光
// 都没你耀眼
// 热爱105°C的你
// 滴滴清纯的蒸馏水
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int,int>;
using ll = long long;
constexpr int N = 1e6 + 10;
int n, m, k;
int du[N];
priority_queue<int> g[N];
vector<array<int,3>> e[N];
vector<int> ns;
bool st[N], ban[N];
void solve() {
cin >> n >> m >> k;
for(int i = 1; i <= m; i ++) ban[i] = false;
for(int i = 1; i <= n; i ++) e[i].clear(), st[i] = false, du[i] = 0;
for(int i = 1; i <= n; i ++) while(g[i].size()) g[i].pop();
ns.clear();
for(int i = 1; i <= k; i ++){
int x;
cin >> x;
ns.push_back(x);
}
for(int i = 1; i <= n; i ++){
cin >> du[i];
du[i] ++;
}
for(int i = 1; i <= m; i ++) {
int l, r, w;
cin >> l >> r >> w;
e[l].push_back({w, r, i});
e[r].push_back({w, l, i});
}
priority_queue<PII,vector<PII>,greater<PII>> q;
for(auto v : ns) {
du[v] = 0;
g[v].push(0);
q.push({0, v});
}
while(q.size()) {
auto [dis, x] = q.top();
if(st[x]) continue;
st[x] = 1;
q.pop();
for(auto [w, v, id] : e[x]) {
if(ban[id]) continue;
ban[id] = true;
du[v] --;
if(du[v] == 0) {
g[v].push(dis + w);
q.push({g[v].top(), v});
}
else if(du[v] < 0 && dis + w < g[v].top()) {
g[v].push(dis + w);
g[v].pop();
q.push({g[v].top(), v});
}
else if (du[v] > 0){
g[v].push(dis + w);
}
}
}
if(du[1] > 0) cout << "-1" << "\n";
else cout << g[1].top() << "\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while(t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 58128kb
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
Time Limit Exceeded
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...