Description

在Byte山的山脚下有一个洞穴入口. 这个洞穴由复杂的洞室经过隧道连接构成. 洞穴的入口是一条笔直通向“前面洞口”的道路. 隧道互相都不交叉(他们只在洞室相遇). 两个洞室要么就通过隧道连接起来,要么就经过若干隧道间接的相连. 现在决定组织办一个'King's of Byteotia Cup' 比赛. 参赛者的目标就是任意选择一条路径进入洞穴并尽快出来即可. 一条路径必须经过除了“前面洞口”之外还至少要经过其他一个洞室.一条路径中一个洞不能重复经过(除了“前面洞室”以外),类似的一条隧道也不能重复经过. 一个著名的洞穴探险家 Byteala 正准备参加这个比赛. Byteala 已经训练了数月而且他已获得了洞穴系统的一套详细资料. 对于每条隧道他都详细计算了从两个方向经过所需要的时间. 经过一个洞室的时间很短可以忽略不记. 现在Byteala 向计算一条符合条件的最优路径.

Input

第一行有两个数n 和 m (3 <= n <= 5000, 3 <= m <= 10000) 分别表示洞室的数目以及连接他们的隧道的数目. 洞室从1 到 n编号. “前面洞室”的编号为1. 接下来m 行描述了所有的隧道. 每行四个整数a,b,c,d 表示从洞室a到洞室b需要c分钟的时间,而从洞室b到洞室a需要d分钟的时间, 1 <= a,b <= n, a <> b, 1 <= c,d <= 10000. 你可以假设符合要求的路径肯定存在.

Output

输出一行,最少需要多少时间完成比赛.

Sample Input

3 3

1 2 4 3

2 3 4 2

1 3 1 1

Sample Output

Solution

这是一个假二进制分组

对一号点相连的点按照二进制来分组

枚举二进制，一种只能由1走向它，另一种只能由它走向1

然后每次都跑一边Dijkstra就好了

因为任意两个点一定在一个数的二进制中在不同的分组，所以方案经过的两个点一定会被枚举到

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

#define ft first

#define sd second

#define pb(a) push_back(a)

#define mp(a,b) std::make_pair(a,b)

#define ITR(a,b) for(auto a:b)

#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)

#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)

const int MAXN=10000+10,MAXM=200000+10,inf=0x3f3f3f3f;

int n,m,e,beg[MAXN],nex[MAXM<<1],to[MAXM<<1],was[MAXM<<1],d[MAXN],dir[MAXN],ans=inf;

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

namespace IO{

    const int Buffsize=1<<15,Output=1<<24;

    static char Ch[Buffsize],*S=Ch,*T=Ch;

    inline char getc()

	{

		return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);

	}

    static char Out[Output],*nowps=Out;

    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)

	{

		x=0;static char ch;T f=1;

		for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;

		for(;isdigit(ch);ch=getc())x=x*10+(ch-'0');

		x*=f;

	}

	template<typename T>inline void write(T x,char ch='\n')

	{

		if(!x)*nowps++='0';

		if(x<0)*nowps++='-',x=-x;

		static int sta[111],tp;

		for(tp=0;x;x/=10)sta[++tp]=x%10;

		for(;tp;*nowps++=sta[tp--]^48);

		*nowps++=ch;

	}

}

using namespace IO;

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline void insert(int x,int y,int z)

{

	to[++e]=y;

	nex[e]=beg[x];

	beg[x]=e;

	was[e]=z;

}

inline void Dijstra(int s)

{

	memset(d,inf,sizeof(d));

	d[s]=0;

	q.push(mp(d[s],s));

	while(!q.empty())

	{

		std::pair<int,int> pr=q.top();

		q.pop();

		if(pr.ft!=d[pr.sd])continue;

		int x=pr.sd;

		for(register int i=beg[x];i;i=nex[i])

			if(to[i]==1)

			{

				if(dir[x])continue;

				if(d[n+1]>d[x]+was[i])d[n+1]=d[x]+was[i];

			}

			else

			{

				if(x==1&&!dir[to[i]])continue;

				if(d[to[i]]>d[x]+was[i])d[to[i]]=d[x]+was[i],q.push(mp(d[to[i]],to[i]));

			}

	}

}

inline void solve(int ps)

{

	for(register int i=beg[1];i;i=nex[i])dir[to[i]]=(to[i]>>ps)&1;

	Dijstra(1);

	chkmin(ans,d[n+1]);

	for(register int i=beg[1];i;i=nex[i])dir[to[i]]^=1;

	Dijstra(1);

	chkmin(ans,d[n+1]);

}

int main()

{

	read(n);read(m);

	REP(i,1,m)

	{

		int u,v,w1,w2;read(u);read(v);read(w1);read(w2);

		insert(u,v,w1);insert(v,u,w2);

	}

	REP(i,0,13)solve(i);

	write(ans,'\n');flush();

	return 0;

}

巴特西

【刷题】BZOJ 2069 [POI2004]ZAW