题意：
给定一张
n
n
n个点，
m
m
m条有向边的图，标记其中
k
k
k个点，求这
k
k
k个点之间的两两最短路的最小值
范围&性质：
1
≤
k
,
n
≤
1
0
5
,
1
≤
m
≤
5
×
1
0
5
1\le k, n\le 10^5,1\le m\le 5\times 10^5
1≤k,n≤105,1≤m≤5×105
分析：
暴力
暴力将关键点分成
A
,
B
A,B
A,B两个集合，超级源向
A
A
A集合每一个点连一条边权为0的边，
B
B
B集合每一个点向超级汇连一条边权为
0
0
0的边，然后从超级源向超级汇跑最短路
正解
我们发现暴力枚举的复杂度不太对，然后我们考虑优化，我们发现正解对应的
s
t
,
e
d
st,ed
st,ed他们的编号必定存在一位不一样，那么我们就枚举二进制位，将这位按照0和1划分成两个集合跑最短路，复杂度
O
(
n
l
o
g
n
2
)
O(nlog^2_n)
O(nlogn2)
代码：
#include<bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
using namespace std
;
namespace zzc
{
const int maxn
= 1e5+5;
const int maxm
= 5e5+5;
int head
[maxn
],key
[maxn
],ghead
[maxn
];
long long dis
[maxn
];
int n
,cnt
=0,t
,st
,ed
,gcnt
,m
,k
;
bool vis
[maxn
];
struct edge
{
int to
,nxt
,val
;
}e
[maxm
+maxn
];
void add(int u
,int v
,int w
)
{
e
[++cnt
].to
=v
;
e
[cnt
].val
=w
;
e
[cnt
].nxt
=head
[u
];
head
[u
]=cnt
;
}
void addedge(int u
,int v
,int w
)
{
e
[++gcnt
].to
=v
;
e
[gcnt
].val
=w
;
e
[gcnt
].nxt
=ghead
[u
];
ghead
[u
]=gcnt
;
}
long long dijkstra()
{
memset(dis
,0x3f,sizeof(dis
));
memset(vis
,false,sizeof(vis
));
dis
[st
]=0;
priority_queue
<pair
<long long,int> > q
;
q
.push(mk(0,st
));
while(!q
.empty())
{
int u
=q
.top().second
;q
.pop();
if(vis
[u
]) continue;
vis
[u
]=true;
for(int i
=ghead
[u
];i
;i
=e
[i
].nxt
)
{
int v
=e
[i
].to
;
if(dis
[v
]>dis
[u
]+e
[i
].val
)
{
dis
[v
]=dis
[u
]+e
[i
].val
;
q
.push(mk(-dis
[v
],v
));
}
}
}
return dis
[ed
];
}
void work()
{
int a
,b
,c
;
scanf("%d",&t
);
while(t
--)
{
cnt
=0;
memset(head
,0,sizeof(head
));
scanf("%d%d%d",&n
,&m
,&k
);
for(int i
=1;i
<=m
;i
++)
{
scanf("%d%d%d",&a
,&b
,&c
);
add(a
,b
,c
);
}
for(int i
=1;i
<=k
;i
++) scanf("%d",&key
[i
]);
long long ans
=LLONG_MAX
;
st
=n
+1;ed
=n
+2;
for(int i
=0;(1<<i
)<=n
;i
++)
{
memcpy(ghead
,head
,sizeof(head
));
gcnt
=cnt
;
for(int j
=1;j
<=k
;j
++)
{
if(j
&(1<<i
))
{
addedge(st
,key
[j
],0);
}
else
{
addedge(key
[j
],ed
,0);
}
}
ans
=min(ans
,dijkstra());
memcpy(ghead
,head
,sizeof(head
));
gcnt
=cnt
;
for(int j
=1;j
<=k
;j
++)
{
if(j
&(1<<i
))
{
addedge(key
[j
],ed
,0);
}
else
{
addedge(st
,key
[j
],0);
}
}
ans
=min(ans
,dijkstra());
}
printf("%lld\n",ans
);
}
}
}
int main()
{
zzc
::work();
return 0;
}
