QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#142757#6523. Escape PlanMaxBlazeResFireWA 494ms78456kbC++231.4kb2023-08-19 20:23:552023-08-19 20:23:57

Judging History

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

  • [2023-08-19 20:23:57]
  • 评测
  • 测评结果:WA
  • 用时:494ms
  • 内存:78456kb
  • [2023-08-19 20:23:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 100005

int n,m,k,ise[MAXN],d[MAXN],dist[MAXN],del[MAXN],vis[MAXN];
vector< pair<int,int> > E[MAXN];
priority_queue<int> Q[MAXN];

inline void upd( int t , int x ){
	if( (int)( Q[t].size() ) <= d[t] ) Q[t].push( x );
	else if( x < Q[t].top() ) Q[t].pop(),Q[t].push( x );
}

int dfs( int x ){
	if( ise[x] ) return 0;
	if( (int)( Q[x].size() ) > d[x] ) return dist[x];
	if( vis[x] || del[x] ) return -1;
	vis[x] = 1;
	for( pair<int,int> p : E[x] ){
		int v = p.first,w = p.second;
		int tmp = dfs( v ); if( tmp == -1 ) continue;
		upd( x , tmp + w );
	}
	vis[x] = 0;
	if( (int)( Q[x].size() ) > d[x] ) return dist[x] = Q[x].top();
	else del[x] = 1; return -1;
}

inline void solve(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for( int i = 1 ; i <= n ; i ++ ){
		dist[i] = -1,ise[i] = del[i] = vis[i] = 0;
		E[i].clear();
		while( !Q[i].empty() ) Q[i].pop();
	}
	for( int i = 1 ; i <= k ; i ++ ){
		int x; scanf("%lld",&x);
		ise[x] = 1;
	}
	for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&d[i]);
	for( int i = 1 ; i <= m ; i ++ ){
		int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
		E[u].emplace_back( make_pair( v , w ) );
		E[v].emplace_back( make_pair( u , w ) );
	}
	printf("%lld\n",dfs(1));
}

signed main(){
	int testcase; scanf("%lld",&testcase);
	while( testcase -- ) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12908kb

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: 494ms
memory: 78456kb

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:

5415
1021
4088
6471
4743
5168
2624
7921
3872
3014
5094
3112
1487
8315
2635
8626
3583
2738
4837
2626
12302
7009
2572
2150
8412
16882
5497
2322
1318
5217
3692
1735
1779
-1
4606
6265
2065
4352
2923
4611
402
3769
-1
8572
8382
5317
-1
510
2636
15128
-1
3166
4107
9746
7991
2356
4208
270
5066
2166
4558
328...

result:

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