题意：
对于边带权的无向图 G = (V, E)，请选择一些边，
使得1<=i<=d,i号节点和 n − i + 1 号节点可以通过选中的边连通，
最小化选中的所有边的权值和。
d<=4 n<=10000 m<=10000 w[i]<=1000
思路：
求一个最小生成树(或森林)，使得若干组点对各自联通
由于d很小(<=4)，考虑采用状压DP的做法。
令1,2,..d和n,n-1...n-d+1为2d个特殊点
先考虑生成树的情况：设F[i][j](i=1,2...n j为一个2d位的2进制)表示以第i个点为根，当前生成树包含特殊点的情况为j的最小代价
一共有两种转移方法：
① F[i][j]+F[i][k]-->F[i][j|k]
② F[i][j]+edg[i][k]-->F[k][j]
初始条件(d=3为例)F[1][000001]=F[2][000010]=F[3][000100]=F[n-2][001000]=F[n-1][010000]=F[n][100000]=0，其余F=inf
从小到大枚举j(0...1<<(2*d)-1)
对每个j，再枚举i和(j的一个子集k)，F[i][j]=min{F[i][k]+F[i][j-k]}
对第二种转移按照多源最短路的方式跑spfa
得到F后再考虑怎么求生成森林答案
令G[i]表示当前点对联通状态为i时的最小代价(如i=011时表示第一个点对(1,n)不连通，第二和三个点对(2,n-1),(3,n-2)连通)
则G[i]=min{G[j]+G[i-j],F[k][p]}(j是i的子集,k=1,2,....n，p表示i代表的点对的所有点的状压形式，如i=001，代表(3,n-2)，此时p=001100)}
最后答案就是G[(1<<d)-1]
时间复杂度：求F O(3^(2*d)*n /*第一步*/ + 2^(2*d)*spfa(n,m) /*第二步*/ )，求G复杂度远低于F，可忽略
空间复杂度：F数组O(n*2^(2*d))，G忽略
const oo=;
var head,vet,next,len:array[..]of longint;
dp:array[..,..]of longint;
g:array[..]of longint;
q:array[..]of longint;
inq:array[..]of boolean;
n,m,sta,i,j,tot,d,x,y,z,s,v,sum:longint; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure add(a,b,c:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
len[tot]:=c;
head[a]:=tot;
end; procedure spfa(sta:longint);
var i,t,w,u,e,v:longint;
begin
t:=; w:=;
for i:= to n do
begin
inc(w); q[w]:=i; inq[i]:=true;
end;
while t<w do
begin
inc(t); u:=q[t mod ]; inq[u]:=false;
e:=head[u];
while e<> do
begin
v:=vet[e];
if dp[u,sta]+len[e]<dp[v,sta] then
begin
dp[v,sta]:=dp[u,sta]+len[e];
if not inq[v] then
begin
inc(w); q[w mod ]:=v; inq[v]:=true;
end;
end;
e:=next[e];
end;
end;
end; begin
assign(input,'road.in'); reset(input);
assign(output,'road.out'); rewrite(output);
readln(n,m,d);
for i:= to m do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,z);
end;
sum:=<<(d<<);
for i:= to sum- do
for j:= to n do dp[j,i]:=oo;
for i:= to d do
begin
dp[i,<<(i-)]:=;
dp[n-i+,<<(i+d-)]:=;
end; for sta:= to sum- do
begin
for i:= to n do
begin
v:=sta-;
while v> do
begin
dp[i,sta]:=min(dp[i,sta],dp[i,v]+dp[i,sta xor v]);
v:=sta and (v-);
end;
end;
spfa(sta);
end;
sum:=<<d;
for sta:= to sum- do
begin
g[sta]:=oo;
for i:= to n do g[sta]:=min(g[sta],dp[i,sta or (sta<<d)]);
end;
for sta:= to sum- do
begin
v:=sta-;
while v> do
begin
g[sta]:=min(g[sta],g[v]+g[sta xor v]);
v:=sta and (v-);
end;
end;
if g[sum-]<oo then writeln(g[sum-])
else writeln(-); close(input);
close(output);
end.