正题
题目链接:https://www.luogu.com.cn/problem/P5304
题目大意
n
n
n个点
m
m
m条边的一张有向图，有
k
k
k个关键点，求距离最短的一对关键点。
解题思路
我们能够
O
(
n
log
n
)
O(n\log n)
O(nlogn)的进行一个起点或多个起点同时的最短路，但是这题显然不能枚举其中的一对点。
可以考虑多个起点的最短路做法，我们可以做到每次计算一组点到另一组点之间的最短路，考虑如何分组能够让每一队都分到过不同的组。
我们可以枚举一个位数
i
i
i，对于第
x
x
x个关键点，如果
x
x
x的第
i
i
i位为
1
1
1那么久分入第一个点组，否则分入第二个点组，那么这样分组就可以做到每个点对都分到过不同的组。
时间复杂度
O
(
n
log
2
n
)
O(n\log^2 n)
O(nlog2n)
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std
;
const ll N
=1e5+10;
struct edge_node
{
ll x
,y
,w
;
}e
[N
*5];
struct node
{
ll to
,next
,w
;
}a
[N
*7];
struct point
{
ll pos
,dis
;
bool operator<(const point
&x
)const
{return x
.dis
<dis
;}
};
priority_queue
<point
> q
;
ll T
,n
,m
,k
,tot
,ans
,s
,t
;
ll z
[N
],ls
[N
],f
[N
];
bool v
[N
];
void addl(ll x
,ll y
,ll w
){
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
a
[tot
].w
=w
;
ls
[x
]=tot
;
}
void Dij(){
memset(f
,0x3f,sizeof(f
));
memset(v
,0,sizeof(v
));
q
.push((point
){s
,0});f
[s
]=0;
while(!q
.empty()){
ll x
=q
.top().pos
,w
=q
.top().dis
;
q
.pop();if(v
[x
])continue;v
[x
]=1;
for(ll i
=ls
[x
];i
;i
=a
[i
].next
){
ll y
=a
[i
].to
;
if(f
[x
]+a
[i
].w
<f
[y
]){
f
[y
]=f
[x
]+a
[i
].w
;
if(!v
[y
])q
.push((point
){y
,f
[y
]});
}
}
}
return;
}
int main()
{
scanf("%lld",&T
);
while(T
--){
scanf("%lld%lld%lld",&n
,&m
,&k
);
s
=0;t
=n
+1;ans
=1e18;
for(ll i
=1;i
<=m
;i
++)
scanf("%lld%lld%lld",&e
[i
].x
,&e
[i
].y
,&e
[i
].w
);
for(ll i
=1;i
<=k
;i
++)scanf("%lld",&z
[i
]);
for(ll p
=0;(1<<p
)<=k
;p
++){
tot
=0;memset(ls
,0,sizeof(ls
));
for(ll i
=1;i
<=m
;i
++)addl(e
[i
].x
,e
[i
].y
,e
[i
].w
);
for(ll i
=1;i
<=k
;i
++)
if((i
>>p
)&1)addl(s
,z
[i
],0);
else addl(z
[i
],t
,0);
Dij();
ans
=min(ans
,f
[t
]);
tot
=0;memset(ls
,0,sizeof(ls
));
for(ll i
=1;i
<=m
;i
++)addl(e
[i
].x
,e
[i
].y
,e
[i
].w
);
for(ll i
=1;i
<=k
;i
++)
if((i
>>p
)&1)addl(z
[i
],t
,0);
else addl(s
,z
[i
],0);
Dij();
ans
=min(ans
,f
[t
]);
}
printf("%lld\n",ans
);
}
}
