题目描述

　　给你一个\(n\)个点\(m\)条边的有向图，有\(k\)个关键点。求一条最短的从一个关键点到另一个关键点的路径。

　　\(n,m,k\leq 100000\)

题解

　　跑\(k^2\)次最短路显然会TLE

　　考虑两个不同的数有什么可以利用的性质。

　　其中会有至少一个二进制为不同！

　　所以可以枚举所有二进制位，从\(0\)的那边向\(1\)的那边跑最短路，再从\(1\)的那边向\(0\)的那边跑最短路。

　　这样最终答案一定会被计算到。

　　时间复杂度：\(O(m\log n\log k)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<queue>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,int> pli;

struct graph

{

	int h[100010];

	int v[100010];

	int w[100010];

	int t[100010];

	int n;

	graph()

	{

		n=0;

		memset(h,0,sizeof h);

	}

	void add(int x,int y,int z)

	{

		n++;

		v[n]=y;

		w[n]=z;

		t[n]=h[x];

		h[x]=n;

	}

};

graph g;

//int lx[100010];

//int ly[100010];

//int lz[100010];

ll d[100010];

int b[100010];

int c[100010];

int n,m,k;

priority_queue<pli,vector<pli>,greater<pli> > q;

ll dij(int y)

{

	int i;

	memset(b,0,sizeof b);

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

		if((i>>(y-1))&1)

			q.push(pli(0,c[i]));

	while(!q.empty())

	{

		pli x=q.top();

		q.pop();

		if(b[x.second])

			continue;

		b[x.second]=1;

		d[x.second]=x.first;

		for(i=g.h[x.second];i;i=g.t[i])

			q.push(pli(x.first+g.w[i],g.v[i]));

	}

	ll ans=0x7fffffffffffffffll;

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

		if(b[c[i]]&&!((i>>(y-1))&1))

			ans=min(ans,d[c[i]]);

	return ans;

}

ll dij2(int y)

{

	int i;

	memset(b,0,sizeof b);

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

		if(!((i>>(y-1))&1))

			q.push(pli(0,c[i]));

	while(!q.empty())

	{

		pli x=q.top();

		q.pop();

		if(b[x.second])

			continue;

		b[x.second]=1;

		d[x.second]=x.first;

		for(i=g.h[x.second];i;i=g.t[i])

			q.push(pli(x.first+g.w[i],g.v[i]));

	}

	ll ans=0x7fffffffffffffffll;

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

		if(b[c[i]]&&(i>>(y-1))&1)

			ans=min(ans,d[c[i]]);

	return ans;

}

int main()

{

	int x,y,z,i;

	scanf("%d%d%d",&n,&m,&k);

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

	{

		scanf("%d%d%d",&x,&y,&z);

		g.add(x,y,z);

	}

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

		scanf("%d",&c[i]);

	ll ans=0x7fffffffffffffffll;

	for(i=1;i<=17;i++)

	{

		ans=min(ans,dij(i));

		ans=min(ans,dij2(i));

	}

	printf("%lld\n",ans);

	return 0;

}