hdu 6166 Senior Pan(多源多汇最短路)

题意：

给你一张有向图，现在选出k个点，问这k个点中，所有的点对的距离中，最短的那条是多少。

题解：

官方题解说的很清楚了。

类比cf 835E，枚举二进制位按照标号当前位为1 和当前位为0分为两个集合，每次求解两个集合之间的最短路即可覆盖到所有的点对。时间复杂度20*dijstla时间

 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int N=2e5+7;ll inf=1ll<<60;
 8 int g[N],v[N],nxt[N],w[N],ed;
 9 int t,n,m,k,a[N],Q[N],in[N],cas;
10 ll d[N];
11 struct EDGE{int a,b,c;}edge[N];
12 
13 void adg(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}
14 
15 ll spfa(int S,int T)
16 {
17     F(i,1,T)d[i]=inf,in[i]=0;
18     d[S]=0,Q[1]=S,in[S]=1;
19     unsigned short l=1,r=2;
20     while(l!=r)
21     {
22         int x=Q[l++];in[x]=0;
23         for(int i=g[x];i;i=nxt[i])
24             if(d[v[i]]>d[x]+w[i])
25             {
26                 d[v[i]]=d[x]+w[i];
27                 if(!in[v[i]])in[v[i]]=1,Q[r++]=v[i];
28             }
29     }
30     return d[T];
31 }
32 
33 int main(){
34     scanf("%d",&t);
35     while(t--)
36     {
37         scanf("%d%d",&n,&m);
38         F(i,1,m)scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
39         scanf("%d",&k);
40         F(i,1,k)scanf("%d",a+i);
41         int S=n+1,T=n+2,pre=ed,now;
42         ll ans=inf;
43         F(i,0,17)
44         {
45             mst(g,0),ed=0,now=1<<i;
46             F(j,1,m)adg(edge[j].a,edge[j].b,edge[j].c);
47             F(j,1,k)
48             {
49                 if(a[j]&now)adg(S,a[j],0);
50                 else adg(a[j],T,0);
51             }
52             ans=min(ans,spfa(S,T));
53             mst(g,0),ed=0;
54             F(j,1,m)adg(edge[j].a,edge[j].b,edge[j].c);
55             F(j,1,k)
56             {
57                 if((a[j]&now)==0)adg(S,a[j],0);
58                 else adg(a[j],T,0);
59             }
60             ans=min(ans,spfa(S,T));
61         }
62         printf("Case #%d: %lld
",++cas,ans);
63     }
64     return 0;
65 }

View Code