QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#228128 | #6523. Escape Plan | sjk1686959421 | WA | 323ms | 31948kb | C++20 | 2.3kb | 2023-10-28 12:21:49 | 2023-10-28 12:21:50 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 500010;
const int INF = 1e16+10;
typedef pair<int,int>PI;
int s[100010],ss[100010],d[100010];
struct cj{
int a,b,c;
}e[1000010];
vector<int>t[100010];
bool cmp(cj x,cj y){
if(x.a!=y.a){
return x.a<y.a;
}
if(x.b!=y.b){
return x.b<y.b;
}
return x.c<y.c;
}
void slove(){
int n,m,k;
cin>>n>>m>>k;
map<PI,int>r;
for(int i=1;i<=n;i++){
s[i]=0;
ss[i]=0;
d[i]=1e16;
t[i].clear();
}
for(int i=1;i<=k;i++){
int x;
cin>>x;
s[x]=1;
}
for(int i=1;i<=n;i++){
cin>>ss[i];
}
for(int i=1;i<=m;i++){
cin>>e[i].a>>e[i].b>>e[i].c;
}
sort(e+1,e+1+m,cmp);
int cnt=0;
/*for(int i=1;i<=m;i++){
cout<<e[i].a<<' '<<e[i].b<<' '<<e[i].c<<endl;
}*/
for(int i=1;i<=m;i++){
int a=e[i].a,b=e[i].b,c=e[i].c;
if(e[i].a==e[i-1].a&&e[i].b==e[i-1].b){
cnt++;
if(ss[a]+1==cnt){
r[{a,b}]=c;
t[a].push_back(b);
}
if(ss[b]+1==cnt){
r[{b,a}]=c;
t[b].push_back(a);
}
}else{
cnt=1;
if(ss[a]+1==cnt){
r[{a,b}]=c;
t[a].push_back(b);
}
if(ss[b]+1==cnt){
r[{b,a}]=c;
t[b].push_back(a);
}
}
}
/*for(auto c:r){
cout<<c.first.first<<' '<<c.first.second<<' '<<c.second<<endl;
}*/
queue<int>w;
d[1]=0;
w.push(1);
int ma=INF;
while(w.size()){
int x=w.front();
//cout<<x<<endl;
if(s[x]){
ma=min(ma,d[x]);
//cout<<d[x]<<endl;
//return;
}
w.pop();
for(int i=0;i<t[x].size();i++){
int y=t[x][i];
//cout<<y<<endl;
if(d[y]>d[x]+r[{x,y}]){
d[y]=d[x]+r[{x,y}];
w.push(y);
}
}
}
if(ma!=INF) cout<<ma<<endl;
else cout<<-1<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--){
slove();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9372kb
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: 323ms
memory: 31948kb
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:
-1 3729 -1 6471 3796 -1 -1 -1 -1 -1 -1 -1 1129 -1 2646 -1 -1 -1 -1 3532 -1 13774 -1 7646 -1 -1 -1 2322 13193 -1 -1 -1 1779 -1 12422 6265 5176 6560 -1 -1 537 3769 -1 12599 -1 -1 -1 510 -1 -1 -1 12229 -1 -1 -1 5770 -1 270 -1 8769 7464 -1 4387 -1 -1 -1 10496 -1 -1 7720 -1 20389 -1 -1 7982 6413 -1 -1 -1...
result:
wrong answer 1st numbers differ - expected: '5109', found: '-1'