QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#143008 | #6523. Escape Plan | MaxBlazeResFire | WA | 1220ms | 78440kb | C++23 | 1.8kb | 2023-08-20 11:18:41 | 2023-08-20 11:18:45 |
Judging History
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;
}
詳細信息
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'