QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#247419#6523. Escape PlangzzzWA 324ms65376kbC++201.6kb2023-11-11 14:21:282023-11-11 14:21:29

Judging History

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

  • [2023-11-11 14:21:29]
  • 评测
  • 测评结果:WA
  • 用时:324ms
  • 内存:65376kb
  • [2023-11-11 14:21:28]
  • 提交

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];
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(int x){
	priority_queue<node,vector<node>> sq;
	sq.push((node){x,0});
	dis[x]=0;
	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--) {
		int n,m,k;cin>>n>>m>>k;
		for(int i=1;i<=n+1;i++){
			e[i].clear();
			dis[i]=1e18;
			num[i]=0;
			ex[i]=false;
			vis[i]=false;
		}
		for(int i=1;i<=k;i++) {
			int fr;cin>>fr;
			e[fr].push_back(pair<int,ll>(n+1,0));
			e[n+1].push_back(pair<int,ll>(fr,0));
			num[fr]=0;
			ex[fr]=true;
		}
		for(int i=1;i<=n;i++){
			int x;cin>>x;
			if(!ex[i]) num[i]=x;
		}
		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));
		}
//		for(int i=0;i<e[3].size();i++){
//			cout<<e[3][i].first<<" "<<e[3][i].second<<"\n";
//		}
		dij(n+1);
		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

 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 324ms
memory: 65376kb

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
351
665
1941
1435
1707
331
3207
745
941
907
941
360
1114
741
2893
809
1138
1904
658
5582
2508
425
1694
2247
10728
842
2322
436
628
1035
490
651
-1
888
6265
532
1400
613
926
402
3769
12745
4341
4005
2016
-1
510
1096
3385
-1
913
773
2946
2248
557
2446
270
1251
1019
1384
954
1472
1895
751
2882
109...

result:

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