[洛谷 5304][GXOI/GZOI2019]旅行者

题目链接

https://www.luogu.com.cn/problem/P5304

题解

一种思路是建一个超级源点和超级汇点，将所有特殊点分为两个集合，求出从源点到汇点的最短路，这个最短路就是其中若干个特殊点对最短路的最小值。

然而只跑一次最短路并不能覆盖到任意的特殊点对，因此需要多次重新划分集合，取所有最短路的最小值作为答案。

一种可行的划分方式是这样的：考虑每个特殊点的编号 \(1,2,\ldots ,k\)，对于每个二进制位，如果两个点在该位上的值相同，就分到同一个集合去。

这样需要跑 \(\log k\) 次最短路。

因为任意两个点的编号不同，故对于任意特殊两个点，都存在一个不同的二进制位，从而使得它们会划分到不同的集合去，从而影响最终的答案。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct graph
{
 struct edge
 {
  int v,w,next;
 }e[1000005];
 struct node
 {
  int u;
  long long dis;
  bool operator<(const node&a)const
  {
   return dis>a.dis;
  }
 };
 int head[100005],vis[100005],cnt;
 long long dis[100005];
 int s,t;
 priority_queue<node> q;
 void init(int n)
 {
  memset(head,0,sizeof(head));
  cnt=0;
  s=n+1,t=n+2;
 }
 void addedge(int u,int v,int w)
 {
  e[++cnt].v=v;
  e[cnt].w=w;
  e[cnt].next=head[u];
  head[u]=cnt;
 }
 long long dijkstra()
 {
  memset(dis,63,sizeof(dis));
  memset(vis,0,sizeof(vis));
  dis[s]=0;
  q.push({s,0});
  while(!q.empty())
  {
   int u=q.top().u;
   q.pop();
   if(vis[u])continue;
   vis[u]=1;
   for(int i=head[u];i;i=e[i].next)
   {
    int v=e[i].v;
    if(dis[v]>dis[u]+e[i].w)
    {
     dis[v]=dis[u]+e[i].w;
     q.push({v,dis[v]});
    }
   }
  }
  return dis[t];
 }
}g,g1;
int p[100005];
int main()
{
 //ios::sync_with_stdio(false);
 int T;
 cin>>T;
 while(T--)
 {
  int n,m,k;
  cin>>n>>m>>k;
  g.init(n);
  g1.init(n);
  int s=n+1,t=n+2;
  for(int i=1;i<=m;i++)
  {
   int u,v,w;
   scanf("%d%d%d",&u,&v,&w);
   g1.addedge(u,v,w);
  }
  for(int i=1;i<=k;i++)
   cin>>p[i];
  long long ans=1e18;
  for(int i=0;(1<<i)<=k;i++)
  {
   g=g1;
   for(int j=1;j<=k;j++)
    if(j&(1<<i))
     g.addedge(s,p[j],0);
    else
     g.addedge(p[j],t,0);
   ans=min(ans,g.dijkstra());
   g=g1;
   for(int j=1;j<=k;j++)
    if(j&(1<<i))
     g.addedge(p[j],t,0);
    else
     g.addedge(s,p[j],0);
   ans=min(ans,g.dijkstra());
  }
  cout<<ans<<endl;
 }
 return 0;
}