QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142580 | #6523. Escape Plan | BUET_POTATOES# | WA | 1257ms | 67280kb | C++20 | 1.4kb | 2023-08-19 12:41:40 | 2023-08-19 12:41:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int>pli;
const ll infl = 1e18;
void solv(){
int n,m,k;
cin>>n>>m>>k;
vector< vector< pii > >g(n+1);
vector<ll>D(n+1, infl);
vector<int>baki(n+1);
vector<int>startnods(k);
for(int &x : startnods) cin>>x;
for(int x : startnods) D[x] = 0;
for(int i=1; i<=n; i++) cin>>baki[i];
for(int i=0; i<m; i++){
int u,v,w;
cin>>u>>v>>w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
priority_queue< pli, vector<pli>, greater<pli> >pq; /// distance, node
for(int x : startnods){
for(auto [v,w] : g[x]) if(D[v]==infl) {
pq.emplace( w, v );
}
}
while(!pq.empty()){
auto [dst, u] = pq.top();
pq.pop();
if(baki[u]){
baki[u]--;
continue;
}
D[u] = dst;
for(auto [v,w] : g[u]) if(D[v]==infl){
pq.emplace( D[u]+w, v );
}
}
if(D[1]==infl){
cout<<"-1\n";
}
else{
cout<<D[1]<<"\n";
}
}
/*
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
*/
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin>>tc;
while(tc--){
solv();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3408kb
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: 1257ms
memory: 67280kb
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:
13919 9039 12183 14028 13329 12072 10786 13408 10693 10661 12170 11759 10333 12396 11478 4580 11539 12073 12692 10455 18674 12942 11330 10757 15335 21490 11668 2322 10673 11049 11532 11308 8353 -1 12341 14285 11850 8993 11654 12808 8124 10795 24260 10965 14460 12766 -1 9076 10125 16724 -1 12235 1288...
result:
wrong answer 1st numbers differ - expected: '5109', found: '13919'