【题解】Luogu P5304 [GXOI/GZOI2019]旅行者

原题传送门

题意：给你k个点，让你求两两最短路之间的最小值

我们考虑二进制拆分，使得每两个点都有机会分在不同的组\((A:0,B:1)\)中，从源点\(S\)向\(A/B\)中的点连边权为0的边，从\(B/A\)中的点向汇点\(T\)连边权为0的边，这时\(S->T\)的最短路就是\(A/B\)中的点到\(B/A\)中的点最短路的最小值

所以做最短路次数为\(2\log k\)，总复杂度为\(T n \log n\log k\)（srf好像还有少一个log的做法，orz srf）

#include <bits/stdc++.h>

#define ll long long

#define N 100005

#define M 700005

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register ll x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline ll Min(register ll a,register ll b)

{

	return a<b?a:b;

}

struct edge{

	int to,next,w;

}e[M];

int head[N],cnt,headn[N],cntn;

inline void add(register int u,register int v,register int w)

{

	e[++cnt]=(edge){v,head[u],w};

	head[u]=cnt;

}

inline void addn(register int u,register int v,register int w)

{

	e[++cntn]=(edge){v,headn[u],w};

	headn[u]=cntn;

}

int T,n,m,k,p[N],s,t;

ll dis[N];

inline ll dijkstra()

{

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

	dis[s]=0;

	priority_queue<pair<ll,int> >q;

	q.push(make_pair(0,s));

	for(register int i=1;i<n+2;++i)

	{

		while(!q.empty()&&dis[q.top().second]!=-q.top().first)

			q.pop();

		if(q.empty())

			break;

		int now=q.top().second;

		q.pop();

		for(register int i=headn[now];i;i=e[i].next)

		{

			int v=e[i].to;

			if(dis[v]>dis[now]+e[i].w)

				q.push(make_pair(-(dis[v]=dis[now]+e[i].w),v));

		}

	}

	return dis[t];

}

int main()

{

	int T=read();

	while(T--)

	{

		cnt=0;

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

		n=read(),m=read(),k=read();

		for(register int i=1;i<=m;++i)

		{

			int u=read(),v=read(),w=read();

			add(u,v,w);

		}

		for(register int i=1;i<=k;++i)

			p[i]=read();

		ll ans=~0ull>>1;

		s=n+1,t=n+2;

		for(register int i=0;(1<<i)<=k;++i)

		{

			cntn=cnt;

			memcpy(headn,head,sizeof(head[0])*(n+3));

			for(register int j=1;j<=k;++j)

				if(j&(1<<i))

					addn(p[j],t,0);

				else

					addn(s,p[j],0);

			ans=Min(ans,dijkstra());

			cntn=cnt;

			memcpy(headn,head,sizeof(head[0])*(n+3));

			for(register int j=1;j<=k;++j)

				if(j&(1<<i))

					addn(s,p[j],0);

				else

					addn(p[j],t,0);

			ans=Min(ans,dijkstra());

		}

		write(ans),puts("");

	}

	return 0;

}

巴特西

【题解】Luogu P5304 [GXOI/GZOI2019]旅行者

原题传送门

题意：给你k个点，让你求两两最短路之间的最小值

我们考虑二进制拆分，使得每两个点都有机会分在不同的组\((A:0,B:1)\)中，从源点\(S\)向\(A/B\)中的点连边权为0的边，从\(B/A\)中的点向汇点\(T\)连边权为0的边，这时\(S->T\)的最短路就是\(A/B\)中的点到\(B/A\)中的点最短路的最小值

所以做最短路次数为\(2\log k\)，总复杂度为\(T n \log n\log k\)（srf好像还有少一个log的做法，orz srf）

最新文章

热门文章