QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#137706 | #6523. Escape Plan | PetroTarnavskyi# | WA | 690ms | 58812kb | C++17 | 1.5kb | 2023-08-10 16:47:27 | 2023-08-10 16:47:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int N = 1 << 17;
int cnt[N];
vector<PII> g[N];
void clear(int n){
FOR(i, 0, n)
g[i].clear();
}
void solve(){
int n, m, k;
cin >> n >> m >> k;
VI es(k);
FOR(i, 0, k){
cin >> es[i];
es[i]--;
}
FOR(i, 0, n)
cin >> cnt[i];
FOR(i, 0, k)
cnt[es[i]] = 0;
FOR(i, 0, m){
int a, b, w;
cin >> a >> b >> w;
a--; b--;
g[a].PB(MP(b, w));
g[b].PB(MP(a, w));
}
multiset<PII> q;
FOR(i, 0, n){
if(cnt[i] == 0){
q.insert(MP(0, i));
}
}
int sz = 0;
while(SZ(q)){
sz++;
int v = q.begin()->S;
int d = q.begin()->F;
q.erase(q.begin());
if(cnt[v] != 0){
cnt[v]--;
continue;
}
cnt[v]--;
if(v == 0){
cout << d << "\n";
clear(n);
return;
}
for(auto e : g[v]){
int to = e.F;
int w = e.S;
if(cnt[to] < 0)
continue;
q.insert(MP(d + w, to));
}
}
cout << "-1\n";
clear(n);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6536kb
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: 690ms
memory: 58812kb
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:
1235 0 1746 1761 0 2299 859 2268 1607 1100 2274 1192 0 1274 1244 2337 932 1432 1790 998 5526 2914 1330 520 4173 10296 2039 0 723 861 1177 922 0 -1 1077 0 397 0 1115 1784 0 0 6168 703 3815 2814 0 0 1683 6658 -1 1599 1950 4549 2944 575 1107 0 2419 485 2074 2459 0 2688 630 3984 703 -1 3524 311 7475 846...
result:
wrong answer 1st numbers differ - expected: '5109', found: '1235'