QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142777#6523. Escape PlanMaxBlazeResFireTL 1ms12444kbC++231.7kb2023-08-19 21:42:452023-08-19 21:42:55

Judging History

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

  • [2023-08-19 21:42:55]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:12444kb
  • [2023-08-19 21:42:45]
  • 提交

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],Vis[MAXN];
struct node{ int v,w,id; };

vector<node> 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( vis[x] ) return -1;
	if( (int)( Q[x].size() ) > d[x] ) return dist[x];
	vis[x] = 1;
	for( node p : E[x] ){
		int v = p.v,w = p.w,id = p.id; if( Vis[id] ) continue;
		//cerr << x << " " << v << "a\n";
		int tmp = dfs( v ); if( tmp == -1 ) continue;
		Vis[id] = 1;
		upd( x , tmp + w );
		//cerr << "upd" << x << "with" << v << "\n";
	}
	vis[x] = 0;
	if( (int)( Q[x].size() ) > d[x] ) return dist[x] = Q[x].top();
	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 ++ ){
		Vis[i] = 0;
		int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
		E[u].emplace_back( node{ v , w , i } );
		E[v].emplace_back( node{ u , w , i } );
	}
	printf("%lld\n",dfs(1));
	// for( int i = 1 ; i <= n ; i ++ ){
		// cerr << i << ":";
		// while( !Q[i].empty() ) cerr << Q[i].top() << " ",Q[i].pop();
		// cerr << "\n";
	// }
}

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

详细

Test #1:

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

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: