[bzoj 4398] 福慧双修

bzoj 4398

思路

求一条从点$1$到点$1$,且至少经过1个非点$1$的点,无重复边的路径,其中一定会包含一条点$1$到点$x_{1}$的边和一条点$x_{2}$到点$1$的边,且$x_{1}\not =x_{2}$。

因为$x_{1}\not =x_{2}$,所以用二进制表示的$x_{1}$和$x_{2}$一定有一位不同,也就是说在这一位上$x_{1}$和$x_{2}$ 中一定有一个是$1$,有一个是$0$。所以我们可以建一个新的起点和一个新的终点,枚举当前位是哪一位,新起点连接所有这一位是$0/1$的,新终点连接这一位是$1/0$的,去掉本来连接在$1$上的所有边,跑最短路即可

时间复杂度为$O(n\cdot log^{2}n)$

代码

#include <iostream>
#include <cstdio>
#include <queue>

struct Node{
	struct Edge *head;
	int dis;
	bool vis;
}node[40010];

struct Edge{
	Node *to;
	Edge *ne;
	int val;
	Edge(int x, int y, int z) : to(&node[y]), ne(node[x].head), val(z){}
};

int N, M;

int solve(int w, int v){
	int ans=0x3f3f3f3f;
	for(int i=1; i<=N; i++)
		node[i].dis=0x3f3f3f3f, node[i].vis=false;
	std::priority_queue<std::pair<int, Node *> >q;
	q.push(std::make_pair(0, &node[1]));
	node[1].dis=0;
	while(!q.empty()){
		Node *x=q.top().second;
		q.pop();
		if(x->vis)	continue;
		x->vis=true;
		for(Edge *i=x->head; i; i=i->ne)
			if(i->to==&node[1] && ((x-&node[0])&(1<<w))==v){
				ans=std::min(ans, x->dis+i->val);
			}else if((x==&node[1] && ((i->to-&node[0])&(1<<w))!=v) ||
				 (x!=&node[1] && i->to!=&node[1])){
				if(i->to->dis>x->dis+i->val){
					i->to->dis=x->dis+i->val;
					q.push(std::make_pair(-i->to->dis, i->to));
				}
			}
	}
	return ans;
}

int main(){
	int x, y, z1, z2;
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++){
		scanf("%d%d%d%d", &x, &y, &z1, &z2);
		node[x].head=new Edge(x, y, z1);
		node[y].head=new Edge(y, x, z2);
	}
	int ans=0x3f3f3f3f;
	for(int i=0; i<=15; i++)
		ans=std::min(ans, std::min(solve(i, 1<<i), solve(i, 0)));
	printf("%d", ans==0x3f3f3f3f ? -1 : ans);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注