QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110131#6523. Escape PlanzzzyzzzWA 629ms34848kbC++172.9kb2023-05-31 18:49:582023-05-31 18:50:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-31 18:50:01]
  • 评测
  • 测评结果:WA
  • 用时:629ms
  • 内存:34848kb
  • [2023-05-31 18:49:58]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'