QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#247495 | #6523. Escape Plan | gzzz | WA | 490ms | 65904kb | C++20 | 1.4kb | 2023-11-11 14:38:54 | 2023-11-11 14:38:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
vector<pair<int,ll>> e[maxn];
ll num[maxn],dis[maxn],n,m,k;;
bool ex[maxn],vis[maxn];
struct node{
int fr;
ll w;
friend bool operator <(node x,node y){
return x.w>y.w;
}
};
void dij(){
priority_queue<node,vector<node>> sq;
for(int i=1;i<=n;i++){
if(ex[i]) {
dis[i]=0;
sq.push((node){i,dis[i]});
}
}
while(!sq.empty()){
int now=sq.top().fr;
sq.pop();
if(vis[now]) continue;
vis[now]=true;
for(int i=0;i<e[now].size();i++){
int to=e[now][i].first,w=e[now][i].second;
if(dis[to]>dis[now]+w){
if(num[to]) {
num[to]--;
}
else {
dis[to]=dis[now]+w;
sq.push((node){to,dis[to]});
}
}
}
}
return ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;cin>>t;
while(t--) {
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
e[i].clear();
dis[i]=1e18;
num[i]=0;
ex[i]=false;
vis[i]=false;
}
for(int i=1;i<=k;i++) {
int x;cin>>x;
ex[x]=true;
}
for(int i=1;i<=n;i++){
cin>>num[i];
}
for(int i=1;i<=m;i++){
int fr,to,w;
cin>>fr>>to>>w;
e[fr].push_back(pair<int,ll>(to,w));
e[to].push_back(pair<int,ll>(fr,w));
}
dij();
if(dis[1]==1e18) cout<<"-1\n";
else cout<<dis[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
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6948kb
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: 490ms
memory: 65904kb
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:
3376 429 1576 1941 1432 1445 331 3207 695 941 1083 941 360 1114 741 2893 809 1138 1904 658 5582 1751 425 1694 2247 10728 842 2322 436 628 1788 490 651 -1 888 6265 532 1445 613 718 402 3769 12745 4341 4320 2016 -1 510 935 3385 -1 913 773 2574 2248 557 2446 270 1251 485 1384 954 1472 1895 751 2882 109...
result:
wrong answer 1st numbers differ - expected: '5109', found: '3376'