[LOJ 2718][UOJ 393][BZOJ 5415][NOI 2018]归程

题意

给定一张无向图, 每条边有一个距离和一个高度. 再给定 \(q\) 组可能在线的询问, 每组询问给定一个点 \(v\) 和一个高度 \(h\), 鸭子德可以先无需花费地在高度大于 \(h\) 的边上任意行动, 然后可以在任意点开始以花费等于距离的模式行动. 问最小的花费.

\(|V|\le 2\times 10^5,|E|\le 4\times 10^5,q\le 4\times 10^5,h\le 10^9\).

题解

显然带花费部分的行动是一个单源最短路. 那么我们只要求出无花费部分的行动可以到达的点中哪一个点距离 \(1\) 最近就可以了.

发现无花费部分是个类似瓶颈路的问题, 我们可以在 Kruskal 重构树上倍增求出能到达的点所组成的子树, 输出这个子树中的点到 \(1\) 的最短距离就可以了.

为啥我要写这个裸题的题解呢?

一个原因是存板子, 另一个原因是这个沙雕强制在线把我卡掉了 \(3\) 分qaq...具体情况

参考代码

#include <bits/stdc++.h>

const int MAXV=4e5+10;

const int MAXE=1e6+10;

struct Edge{

	int from;

	int to;

	int dis;

	int pos;

	Edge* next;

	bool friend operator>(const Edge& a,const Edge& b){

		return a.pos>b.pos;

	}

};

Edge E[MAXE];

Edge Ex[MAXE];

Edge* head[MAXV];

Edge* top=E;

int v;

int e;

int q;

int n;

int k;

int maxv;

int dis[MAXV];

int pos[MAXV];

int ufs[MAXV];

bool vis[MAXV];

int pprt[20][MAXV];

int* prt=pprt[0];

int ReadInt();

void Kruskal();

int FindRoot(int);

void Dijkstra(int);

void Insert(int,int,int,int);

int main(){

	int T=ReadInt();

	while(T--){

		memset(pprt,0,sizeof(pprt));

		memset(head,0,sizeof(head));

		memset(vis,0,sizeof(vis));

		top=E;

		n=v=ReadInt();

		e=ReadInt();

		for(int i=0;i<e;i++){

			int a=ReadInt(),b=ReadInt(),c=ReadInt(),d=ReadInt();

			Ex[i]=Edge({a,b,c,d,NULL});

			Insert(a,b,c,d);

			Insert(b,a,c,d);

		}

		q=ReadInt(),k=ReadInt(),maxv=ReadInt();

		Dijkstra(1);

		Kruskal();

		int lg=0;

		for(int i=1;(1<<i)<=v;i++){

			lg=i;

			for(int j=1;j<=v;j++)

				pprt[i][j]=pprt[i-1][pprt[i-1][j]];

		}

		int lastans=0;

		while(q--){

			int s=(0ll+ReadInt()+k*lastans-1)%n+1,h=(0ll+ReadInt()+k*lastans)%(maxv+1);

			for(int i=lg;i>=0;i--){

				if(pos[pprt[i][s]]>h)

					s=pprt[i][s];

			}

			printf("%d\n",lastans=dis[s]);

		}

	}

	return 0;

}

void Kruskal(){

	std::sort(Ex,Ex+e,std::greater<Edge>());

	for(int i=1;i<=v;i++)

		ufs[i]=i;

	int& cur=v;

	for(int i=0;i<e;i++){

		int a=FindRoot(Ex[i].from);

		int b=FindRoot(Ex[i].to);

		if(a!=b){

			++cur;

			pos[cur]=Ex[i].pos;

			dis[cur]=std::min(dis[a],dis[b]);

			prt[a]=cur;

			prt[b]=cur;

			ufs[cur]=cur;

			ufs[a]=cur;

			ufs[b]=cur;

		}

	}

}

void Dijkstra(int s){

	std::priority_queue<std::pair<int,int>> q;

	memset(dis,0x7F,sizeof(dis));

	dis[s]=0;

	q.emplace(0,s);

	while(!q.empty()){

		s=q.top().second;

		q.pop();

		if(vis[s])

			continue;

		vis[s]=true;

		for(Edge* i=head[s];i!=NULL;i=i->next){

			if(dis[i->to]>dis[s]+i->dis){

				dis[i->to]=dis[s]+i->dis;

				q.emplace(-dis[i->to],i->to);

			}

		}

	}

}

inline void Insert(int from,int to,int dis,int pos){

	top->from=from;

	top->to=to;

	top->dis=dis;

	top->pos=pos;

	top->next=head[from];

	head[from]=top++;

}

int FindRoot(int x){

	return ufs[x]==x?ufs[x]:ufs[x]=FindRoot(ufs[x]);

}

inline int ReadInt(){

	int x=0;

	register char ch=getchar();

	while(!isdigit(ch))

		ch=getchar();

	while(isdigit(ch)){

		x=x*10+ch-'0';

		ch=getchar();

	}

	return x;

}

巴特西

[LOJ 2718][UOJ 393][BZOJ 5415][NOI 2018]归程

[LOJ 2718][UOJ 393][BZOJ 5415][NOI 2018]归程

题意

题解

参考代码

最新文章

热门文章