QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110130#6523. Escape PlanzzzyzzzML 2ms5596kbC++172.1kb2023-05-31 18:38:522023-05-31 18:38:54

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:38:54]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:5596kb
  • [2023-05-31 18:38:52]
  • 提交

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...

output:


result: