QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#137689#6523. Escape PlanPetroTarnavskyi#ML 0ms6524kbC++171.4kb2023-08-10 16:37:572023-08-10 16:37:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 16:37:59]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:6524kb
  • [2023-08-10 16:37:57]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: