QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109313#6523. Escape PlanxuxubaobaoTL 8ms58128kbC++171.7kb2023-05-28 12:57:212023-05-28 12:57:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-28 12:57:25]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:58128kb
  • [2023-05-28 12:57:21]
  • 提交

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

output:


result: