QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#228113 | #6523. Escape Plan | sjk1686959421 | WA | 313ms | 32152kb | C++20 | 2.5kb | 2023-10-28 12:12:00 | 2023-10-28 12:12:01 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 500010;
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(i==0){
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);
}
}
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);
while(w.size()){
int x=w.front();
//cout<<x<<endl;
if(s[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);
}
}
}
cout<<"-1"<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--){
slove();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7976kb
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: 313ms
memory: 32152kb
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 9039 -1 6471 5555 -1 -1 -1 -1 -1 -1 -1 3249 -1 5513 -1 -1 -1 -1 3952 -1 13774 -1 14329 -1 -1 -1 2322 13546 -1 -1 -1 4157 -1 18783 6265 6264 8993 -1 -1 8124 3769 -1 12599 -1 -1 -1 510 -1 -1 -1 14645 -1 -1 -1 5770 -1 270 -1 11967 10221 -1 6710 -1 -1 -1 10521 -1 -1 11903 -1 21551 -1 -1 7982 12604 -1...
result:
wrong answer 1st numbers differ - expected: '5109', found: '-1'