QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#247419 | #6523. Escape Plan | gzzz | WA | 324ms | 65376kb | C++20 | 1.6kb | 2023-11-11 14:21:28 | 2023-11-11 14:21:29 |
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];
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(int x){
priority_queue<node,vector<node>> sq;
sq.push((node){x,0});
dis[x]=0;
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(num[to]) {
num[to]--;
}
else {
if(dis[to]>dis[now]+w){
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--) {
int n,m,k;cin>>n>>m>>k;
for(int i=1;i<=n+1;i++){
e[i].clear();
dis[i]=1e18;
num[i]=0;
ex[i]=false;
vis[i]=false;
}
for(int i=1;i<=k;i++) {
int fr;cin>>fr;
e[fr].push_back(pair<int,ll>(n+1,0));
e[n+1].push_back(pair<int,ll>(fr,0));
num[fr]=0;
ex[fr]=true;
}
for(int i=1;i<=n;i++){
int x;cin>>x;
if(!ex[i]) num[i]=x;
}
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));
}
// for(int i=0;i<e[3].size();i++){
// cout<<e[3][i].first<<" "<<e[3][i].second<<"\n";
// }
dij(n+1);
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: 6592kb
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: 324ms
memory: 65376kb
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 351 665 1941 1435 1707 331 3207 745 941 907 941 360 1114 741 2893 809 1138 1904 658 5582 2508 425 1694 2247 10728 842 2322 436 628 1035 490 651 -1 888 6265 532 1400 613 926 402 3769 12745 4341 4005 2016 -1 510 1096 3385 -1 913 773 2946 2248 557 2446 270 1251 1019 1384 954 1472 1895 751 2882 109...
result:
wrong answer 1st numbers differ - expected: '5109', found: '3376'