QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#247500 | #6523. Escape Plan | gzzz | WA | 0ms | 5924kb | C++20 | 1.4kb | 2023-11-11 14:39:49 | 2023-11-11 14:39:50 |
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(num[now]) {
num[now]--;
continue;
}
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){
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 5924kb
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:
-1 1
result:
wrong answer 1st numbers differ - expected: '4', found: '-1'