题意：给定一个n个点，m条边的有向图，有k个被标记的点，求这k个点中任意两个点之间的最短路径的最小值。
n<=100,000 m<=500,000
暴力的思路:对于每个被标记的点都跑一遍dij,然后在其它被标记的点中取min,复杂度 O(k*(n+m)logn)
对于暴力的优化：我们可以对这k个标记点进行二进制分组，分为两组，每次从set1向set2跑最短路取min,
再从set2向set1跑一遍最短路取min,因为若存在两个点之间的最短路为最小值，这两个点的下标的二进制
位一定有一位不一样，从而不被分在同一个组里，正确性被证明，这样只需要跑logk次即可。
复杂度 O(logk*(n+m)logn)；
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #define maxn 100010 #define INF 2147483647 using namespace std; struct node { int ed,len,nxt; }; node edge[maxn*5]; int n,m,k,first[maxn],cnt,dis[maxn]; int love[maxn]; int set1_cnt,set2_cnt; int set1[maxn],set2[maxn]; bool vis[maxn]; inline void add_edge(int s,int e,int d) { cnt++; edge[cnt].ed=e; edge[cnt].len=d; edge[cnt].nxt=first[s]; first[s]=cnt; return; } inline void dijkstra() { priority_queue < pair <int,int> > heap; for(register int i=1;i<=n;++i) dis[i]=INF,vis[i]=false; for(register int i=1;i<=set1_cnt;++i) { dis[set1[i]]=0; heap.push(make_pair(-dis[set1[i]],set1[i])); } while(!heap.empty()) { int p=heap.top().second; heap.pop(); if(vis[p]) continue; vis[p]=true; for(register int i=first[p];i;i=edge[i].nxt) { int e=edge[i].ed; int d=edge[i].len; int newd=dis[p]+d; if(newd<dis[e]) { dis[e]=newd; heap.push(make_pair(-dis[e],e)); } } } return; } inline void dijkstra_2() { priority_queue < pair <int,int> > heap; for(register int i=1;i<=n;++i) dis[i]=INF,vis[i]=false; for(register int i=1;i<=set2_cnt;++i) { dis[set2[i]]=0; heap.push(make_pair(-dis[set2[i]],set2[i])); } while(!heap.empty()) { int p=heap.top().second; heap.pop(); if(vis[p]) continue; vis[p]=true; for(register int i=first[p];i;i=edge[i].nxt) { int e=edge[i].ed; int d=edge[i].len; int newd=dis[p]+d; if(newd<dis[e]) { dis[e]=newd; heap.push(make_pair(-dis[e],e)); } } } return; } int main() { int t; scanf("%d",&t); while(t--) { memset(edge,0,sizeof(edge)); memset(first,0,sizeof(first)); cnt=0; scanf("%d%d%d",&n,&m,&k); for(register int i=1;i<=m;++i) { int s,e,d; scanf("%d%d%d",&s,&e,&d); add_edge(s,e,d); } int ans=2147483647; for(register int i=1;i<=k;++i) scanf("%d",&love[i]); for(register int i=0;(1<<i)<=k;++i) { set1_cnt=0; set2_cnt=0; for(register int j=1;j<=k;++j) { if(((j>>i)&1)==0) set1[++set1_cnt]=love[j]; else set2[++set2_cnt]=love[j]; } dijkstra(); for(register int j=1;j<=set2_cnt;++j) ans=min(ans,dis[set2[j]]); dijkstra_2(); for(register int j=1;j<=set1_cnt;++j) ans=min(ans,dis[set1[j]]); } printf("%d\n",ans); } return 0; }
原文：https://www.cnblogs.com/Hoyoak/p/11774033.html