QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#247486#6523. Escape PlangzzzWA 328ms66444kbC++201.4kb2023-11-11 14:36:542023-11-11 14:36:54

Judging History

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

  • [2023-11-11 14:36:54]
  • 评测
  • 测评结果:WA
  • 用时:328ms
  • 内存:66444kb
  • [2023-11-11 14:36:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
vector<pair<int,ll>> e[maxn];
ll num[maxn],dis[maxn],n,m,k;;
bool ex[maxn],vis[maxn];
struct node{
	int fr;
	ll w;
	friend bool operator <(node x,node y){ 	
		return x.w>y.w;
	}
};
void dij(){
	priority_queue<node,vector<node>> sq;
	for(int i=1;i<=n;i++){
		if(ex[i]) {
			dis[i]=0;
			sq.push((node){i,dis[i]});
		}
	}
	while(!sq.empty()){
		int now=sq.top().fr;
		sq.pop();
		if(vis[now]) continue;
		vis[now]=true;
		for(int i=0;i<e[now].size();i++){
			int to=e[now][i].first,w=e[now][i].second;
			if(num[to]) {
				num[to]--;
			}
			else {
				if(dis[to]>dis[now]+w){
					dis[to]=dis[now]+w;
					sq.push((node){to,dis[to]});
				}
			}
		}
	}
	return ;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;cin>>t;
	while(t--) {
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++){
			e[i].clear();
			dis[i]=1e18;
			num[i]=0;
			ex[i]=false;
			vis[i]=false;
		}
		for(int i=1;i<=k;i++) {
			int x;cin>>x;
			ex[x]=true;
		}
		for(int i=1;i<=n;i++){
			cin>>num[i];
		}
		for(int i=1;i<=m;i++){
			int fr,to,w;
			cin>>fr>>to>>w;
			e[fr].push_back(pair<int,ll>(to,w));
			e[to].push_back(pair<int,ll>(fr,w));
		}
		dij();
		if(dis[1]==1e18) cout<<"-1\n";
		else cout<<dis[1]<<"\n";
	}
}
/*
  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

 */

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7880kb

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: 328ms
memory: 66444kb

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:

3376
429
1576
1941
1432
1445
331
3207
695
941
1083
941
360
1114
741
2893
809
1138
1904
658
5582
1751
425
1694
2247
10728
842
2322
436
628
1788
490
651
-1
888
6265
532
1445
613
718
402
3769
12745
4341
4320
2016
-1
510
935
3385
-1
913
773
2574
2248
557
2446
270
1251
485
1384
954
1472
1895
751
2882
109...

result:

wrong answer 1st numbers differ - expected: '5109', found: '3376'