TLE sub5 一个点求助
查看原帖
TLE sub5 一个点求助
450705
__phiu楼主2023/10/30 14:29

rt

#include<bits/stdc++.h>
#define mp make_pair
#define For(i,a,b,c) for(int i=a;i<=b;i+=c)
#define Rof(i,a,b,c) for(int i=a;i>=b;i-=c)
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N = 1e5 + 50;
inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	while (c<'0' or c>'9') {
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' and c <= '9')
		x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x * f;
}
int n,q,m;
int to[N<<1],from[N<<1],head[N],val[N<<1];
int tot ;
void add(int x,int y,int v) {
	to[++tot] = y;
	from[tot] = head[x] ;
	val[tot] = v;
	head[x] = tot ;
}
int minn[N<<2] ,a[N];
void up(int p) {
	minn[p] = min (minn[p<<1] , minn[p<<1|1] ) ;
	return ;
}
void build (int p,int l,int r){
	if(l == r) {
		minn[p] = a[l] ;
		return ;
	}
	int mid = l+r >>1 ;
	build (p<<1,l,mid) ;
	build (p<<1|1,mid+1,r) ;
	up(p); 
}
int query(int p,int l,int r,int L,int R) {
	if(l>=L && r<=R) {
		return minn[p] ;
	}
	int mid=l+r>>1;
	int ans = 2e9 ;
	if(L<=mid)
		ans=min(ans,query(p<<1,l,mid,L,R)) ;
	if(R>mid)
		ans=min(ans,query(p<<1|1,mid+1,r,L,R)) ;
	return ans ;
}
int siz[N],son[N] ;
int fa[N];
int dep[N],d[N];

int nod[N];
struct node{
	int pos,dis;
	bool operator < (const node &a) const {
		return dis>a.dis ;
	}
};
bool vis[N];
int dis[N];
void dij(){
	priority_queue<node> q;
	memset(dis,0x3f,sizeof dis) ;
	for(int i=1;i<=m;i++) {
		dis[nod[i]] = 0;
		q.push(node{nod[i],0}) ;
	}
	while(!q.empty()) {
		node p=q.top() ;
		q.pop() ;
		int x=p.pos ;
		vis[x] = 1 ;
		for(int i=head[x];i;i=from[i]) {
			if(dis[x] + val[i] < dis[to[i]]) {
				dis[to[i]] = dis[x] + val[i] ;
				if(!vis[to[i]])
					q.push(node{to[i],dis[to[i]]}) ;
			}
		}	
	}
}
void dfs1(int x,int f){
	fa[x] = f;
	dep[x] = dep[f] + 1 ;
	for(int i=head[x];i;i=from[i]) {
		if(to[i] == f) continue ;
		d[to[i]] = d[x] + val[i] ;
		dfs1(to[i],x) ;
		siz[x] += siz[to[i]] ;
		if(siz[to[i]] > siz[son[x]]) son[x] = to[i] ;
	}
	return ;
}
int top[N];
int dfn[N] ;
int idx; 
void dfs2(int x,int tp) {
	dfn[x] = ++idx ;
	a[idx] = dis[x] ;
	top[x] = tp;
	if(son[x])
		dfs2(son[x],tp) ;
	for(int i=head[x];i;i=from[i]) {
		if(to[i] == fa[x] || to[i] == son[x]) continue ;
		dfs2(to[i],to[i]) ;
	}
	return ;
}
int LCA(int x,int y){
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]])
			swap(x,y);
		x=fa[top[x]] ;
	}
	if(dep[x] > dep[y]) swap(x,y) ;
	return x;
}
int dist(int x,int y) {
	int ans = 2e9 , res = d[x] + d[y] - 2 * d[LCA(x,y)] ;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) 
			swap(x,y) ;
		ans = min(ans,query(1,1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]] ;
	}
	if(dep[x]>dep[y]) swap(x,y) ;
	ans = min(ans,query(1,1,n,dfn[x],dfn[y])) ;
	return res + ans * 2;
}
signed main() {
	n=read() , q=read() , m=read() ;
	for(int i=1;i<n;i++) {
		int x=read(),y=read(),v=read();
		add(x,y,v),add(y,x,v) ;
	}
	for(int i=1;i<=m;i++) nod[i] = read() ;
	dij() ;
	dfs1(1,0) ;
	dfs2(1,1) ;
	build(1,1,n) ;
	while(q--) {
		int x=read(),y=read() ;
		printf("%d\n",dist(x,y)) ;
	}
	return 0;
}
2023/10/30 14:29
加载中...