taking_over_w
% taking_over_w.pi (in Picat)
% by N.F. Zhou, Dec. 2, 2015
% https://code.google.com/codejam/contest/5224486/dashboard#s=p3
% Problem D. Taking Over The World
% World Finals 2015
% to use: picat taking_over_w < input_file > output_file
%
import util.
main =>
T = to_integer(read_line()),
foreach (CN in 1..T)
[N,M,K] = [to_integer(S) : S in read_line().split()],
Edges = [$edge(From,To): _ in 1..M,
[V1,V2] = [to_integer(S) : S in read_line().split()],
[From,To] in [[V1,V2],[V2,V1]]],
cl_facts(Edges,$[edge(+,-)]),
do_case(CN,N,K)
end.
do_case(CN,N,K) =>
initialize_table,
maxof(osp(N,K,Cost),Cost),
printf("Case #%w: %w\n",CN,Cost).
osp(N,K,Cost) =>
N1 = N-1,
osp(0,N1,[],Min),
% filter out vertices that are not on any shortest paths
Set = [V : V in 1..N-2,
osp(0,V,[],Min1),osp(V,N1,[],Min2),
Min1+Min2==Min],
M = len(Set),
(M >= K -> subset(Set,M,K-1,ObsSet); ObsSet=Set),
osp(0,N-1,[0|ObsSet],Cost).
% Subset is a subset of K elements from Set (|Set| = M).
subset(Set,M,K,Subset), K==M => Subset = Set.
subset(_,_M,0,Subset) => Subset = [].
subset([E|Set],M,K,Subset) ?=>
Subset = [E|SubsetR],
subset(Set,M-1,K-1,SubsetR).
subset([_|Set],M,K,Subset) =>
subset(Set,M-1,K,Subset).
table (+,+,+,min)
osp(To,To,_ObsSet,Cost) => Cost=0.
osp(From,To,ObsSet,Cost) =>
edge(From,Next),
osp(Next,To,ObsSet,Cost1),
(membchk(From,ObsSet) ->
Cost = Cost1+2
;
Cost = Cost1+1
).