QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137689 | #6523. Escape Plan | PetroTarnavskyi# | ML | 0ms | 6524kb | C++17 | 1.4kb | 2023-08-10 16:37:57 | 2023-08-10 16:37:59 |
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));
}
}
while(SZ(q)){
int v = q.begin()->S;
int d = q.begin()->F;
q.erase(q.begin());
if(cnt[v] != 0){
cnt[v]--;
continue;
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6524kb
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
Memory 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...