QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#143008#6523. Escape PlanMaxBlazeResFireWA 1220ms78440kbC++231.8kb2023-08-20 11:18:412023-08-20 11:18:45

Judging History

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

  • [2023-08-20 11:18:45]
  • 评测
  • 测评结果:WA
  • 用时:1220ms
  • 内存:78440kb
  • [2023-08-20 11:18:41]
  • 提交

answer

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

#define int long long
#define MAXN 100005

int n,m,k,d[MAXN],exi[MAXN],ise[MAXN],vis[MAXN];
priority_queue<int> Q[MAXN];

set< pair<int,int> > S;
vector< pair<int,int> > E[MAXN];

inline void upd( int x , int t ){
	if( (int)( Q[x].size() ) <= d[x] ) Q[x].push( t );
	else if( t < Q[x].top() ) Q[x].pop(),Q[x].push( t );
	if( (int)( Q[x].size() ) <= d[x] ) return;
	t = Q[x].top();
	set< pair<int,int> >::iterator It = S.lower_bound( make_pair( x , -1 ) );
	if( It != S.end() && It -> first == x && It -> second < t ) S.erase( It );
	S.insert( make_pair( x , t ) );
}

inline void solve(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for( int i = 1 ; i <= k ; i ++ ) scanf("%lld",&exi[i]),ise[exi[i]] = 1;
	for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&d[i]);
	for( int i = 1 ; i <= k ; i ++ ) d[exi[i]] = 0;
	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 ) );
	}
	for( int i = 1 ; i <= n ; i ++ )
		if( ise[i] ) upd( i , 0 );
	while( S.size() ){
		set< pair<int,int> >::iterator it = S.begin();
		int u = it -> first,W = it -> second; S.erase( it );
		if( vis[u] ) continue;
		vis[u] = 1;
		for( pair<int,int> p : E[u] ){
			int v = p.first,w = p.second;
			//cerr << "update " << v << " with " << u << " and value " << W + w << "\n";
			upd( v , W + w );
		}
	}
	if( (int)( Q[1].size() ) <= d[1] ) printf("-1\n");
	else printf("%lld\n",Q[1].top());
	for( int i = 1 ; i <= n ; i ++ ) ise[i] = exi[i] = vis[i] = d[i] = 0;
	for( int i = 1 ; i <= n ; i ++ ) E[i].clear();
	for( int i = 1 ; i <= n ; i ++ )
		while( !Q[i].empty() ) Q[i].pop();
	S.clear();
}

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: 11564kb

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: 1220ms
memory: 78440kb

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:

7546
1021
6676
7333
4908
5301
3271
7487
5221
3989
6139
4603
1487
5937
2646
12012
3088
3611
5107
4869
12310
8461
2572
2150
7937
18912
5707
2322
2133
3789
5764
3250
1779
-1
8977
6265
2065
5241
2777
7081
402
3769
19209
8572
8421
5974
-1
510
3467
18604
-1
5131
4120
10946
7645
2356
3302
270
5511
2639
634...

result:

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