QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#142788 | #6523. Escape Plan | MaxBlazeResFire | TL | 1ms | 12960kb | C++23 | 1.5kb | 2023-08-19 22:02:15 | 2023-08-19 22:02:18 |
Judging History
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( (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[v] ) continue;
int tmp = dfs( v );
if( tmp == -1 ) continue;
//cerr << "upd" << x << "with" << v << "\n";
if( !Vis[id] ) Vis[id] = 1,upd( x , tmp + w );
}
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 << dist[i] << "\n";
}
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: 1ms
memory: 12960kb
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...