QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110130 | #6523. Escape Plan | zzzyzzz | ML | 2ms | 5596kb | C++17 | 2.1kb | 2023-05-31 18:38:52 | 2023-05-31 18:38:54 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5+7,M=3e6+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];
void add(int a,int b,int c) {
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void bfs(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 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(),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);
}
bfs(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);
// }
dfs(1,-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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5596kb
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
Memory Limit Exceeded
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...