QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110131 | #6523. Escape Plan | zzzyzzz | WA | 629ms | 34848kb | C++17 | 2.9kb | 2023-05-31 18:49:58 | 2023-05-31 18:50:01 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5+7,M=2e6+7;
typedef long long ll;
typedef pair<int,int> PII;
inline ll read() {
ll c=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
c=c*10+ch-'0';
ch=getchar();
}
return c*f;
}
int n,m,k;
int h[N],e[M],ne[M],w[M],idx;
int cost[N];
bool st[N];
bool temp[N];
int cnt[N];
ll dist[N];
bool stt[N];
void add(int a,int b,int c) {
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void bfs1(vector<int> &vis) {
queue<int> q;
for(auto &it:vis) q.push(it);
while(q.size()) {
auto it=q.front();
q.pop();
if(st[it]) continue;
st[it]=true;
for(int i=h[it];i!=-1;i=ne[i]) {
int j=e[i];
if(temp[it]) {
cnt[j]++;
if(cost[j]<cnt[j]) {
temp[j]=true;
q.push(j);
}
}
}
}
}
//void dfs(int u,int fa) {
// priority_queue<PII,vector<PII>,greater<PII> > q;
// for(int i=h[u];i!=-1;i=ne[i]) {
// int j=e[i];
//
// if(j==fa) continue;
// q.push({w[i],j});
// }
//
// for(int i=1;i<=cost[u]&&q.size();i++) q.pop();
//
// while(q.size()) {
// auto it=q.top();
// q.pop();
//
// int wi=it.fi;
// int j=it.se;
//// printf("u = %d,j = %d\n",u,j);
// dist[j]=min(dist[j],dist[u]+wi);
// if(temp[j]) dfs(j,u);
// }
//}
void bfs2(int u) {
queue<int> q;
q.push(1);
while(q.size()) {
int it=q.front();
q.pop();
// printf("it = %d\n",it);
if(stt[it]) continue;
stt[it]=true;
priority_queue<PII,vector<PII>,greater<PII> > q1;
for(int i=h[it];i!=-1;i=ne[i]) {
int j=e[i];
if(stt[j]) continue;
q1.push({w[i],j});
}
for(int i=1;i<=cost[it]&&q1.size();i++) q1.pop();
while(q1.size()) {
auto its=q1.top();
q1.pop();
int wi=its.fi;
int j=its.se;
// printf("it = %d,j = %d,wi = %d\n",it,j,wi);
// printf("u = %d,j = %d\n",u,j);
dist[j]=min(dist[j],dist[it]+wi);
if(temp[j]) {
q.push(j);
// printf("it = %d,j = %d\n",it,j);
}
}
}
}
void solve() {
n=read(),m=read(),k=read();
memset(dist,0x3f3f,sizeof(ll)*(n+4));
vector<int> vis;
for(int i=1;i<=k;i++) {
int c=read();
vis.push_back(c);
}
for(int i=1;i<=n;i++) cost[i]=read(),stt[i]=false,cnt[i]=0,temp[i]=false,st[i]=false;
for(auto &it:vis) temp[it]=true;
memset(h,-1,sizeof(int)*(n+4));
idx=0;
while(m--) {
int a=read(),b=read(),c=read();
add(a,b,c),add(b,a,c);
}
bfs1(vis);
if(!temp[1]) {
printf("-1\n");
return ;
}
dist[1]=0;
// for(int i=1;i<=n;i++) {
// if(temp[i]) printf("i = %d\n",i);
// }
bfs2(1);
ll res=0x3f3f3f3f3f3f3f3f;
for(auto &it:vis) res=min(res,dist[it]);
printf("%lld\n",res);
}
int main() {
int T;
T=read();
while(T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7720kb
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: 629ms
memory: 34848kb
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:
3488 1021 2655 1941 2491 1221 331 5365 866 1197 1119 1398 555 2060 1526 3792 2110 1988 2957 723 5385 2508 1376 2150 3981 10088 1839 2322 863 1375 2921 703 1266 -1 2291 4887 1414 791 2146 1567 402 2663 3129 3583 3952 3213 -1 510 1323 5446 -1 808 1764 1397 3703 2303 623 270 3668 485 2113 1535 2063 268...
result:
wrong answer 1st numbers differ - expected: '5109', found: '3488'