QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142777 | #6523. Escape Plan | MaxBlazeResFire | TL | 1ms | 12444kb | C++23 | 1.7kb | 2023-08-19 21:42:45 | 2023-08-19 21:42:55 |
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( 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...