【GDOI2014模拟】旅行
Description
从前有一位旅者，他想要游遍天下所有的景点。这一天他来到了一个神奇的王国：在这片土地上，有n个城市，从1到n进行编号。王国中有m条道路，第i条道路连接着两个城市ai,bi，由于年代久远，所有的道路都已经不能使用。如果要修复第i条道路，需要wi的时间。为了更好的旅行，旅者想要将某些道路修复，使得1号城市能够到达n号城市，2号城市能够到达n-1号城市..k号城市能够到达n-k+1号城市。为了满足他的要求，请问最少需要多少时间去修复道路。无解请输出-1。
Input
第一行：n,m,k 接下来m行：ai,bi,wi 含义如上所述。
Output
输出共一行：最少需要多少时间修复道路。如果始终无法满足旅者的要求，请输出-1。
Sample Input
5 5 2 1 3 4 3 5 2 2 3 1 3 4 4 2 4 3
Sample Output
9
Data Constraint
20%的数据满足：k ⇐ 2, n<= 10, m ⇐ 20 40%的数据满足：k ⇐ 3, n<=100, m<=1000 70%的数据满足：k<=4, n<=1000, m<=1000 100%的数据满足：k<=4, n<=10000, m<=10000, n >= 2*k, wi<= 1000, 1 ⇐ ai, bi ⇐ n
Hint
样例解释：
题解
考场上看到这题先是想到了最小生成树，然后乱搞，然后就没有然后了……
正解似乎是斯坦纳树板子题，但我不会
下面提供一种连拍都过不了但是过掉数据的水法
我们发现k非常小，也就是说关键点个数非常少，于是我们可以将每对关键点的遍历顺序$k!$做一个全排列，之后在每一对点中跑一遍spfa，经过的边加到答案里面，然后全部赋值为0，最后取最小的答案
（什么？你问我这个操作怎么做？随便写个链表就行了）
错误性显然
CODE（水法）
#include<cstdio>
#include<string>
#include<queue>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define R register int
#define N 10005
#define K 5
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
struct arr{int x,y,z;}bian[N];
struct G{int to,next,w;}e[N<<1];
int n,m,k,ans,f[K],cnt,head[N],dist[N],nxt[N][2];
bool change[K],bz[N];
inline void read(int &x)
{
x=0;int f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
inline void add(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].w=w;
e[cnt].next=head[u];head[u]=cnt;
}
inline int spfa(int st,int en)
{
queue<int>q;
for (R i=1;i<=n;++i)
dist[i]=inf,bz[i]=0;
q.push(st);dist[st]=0;bz[st]=1;
while (!q.empty())
{
int u=q.front();q.pop();
for (R i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if (dist[v]>dist[u]+e[i].w)
{
dist[v]=dist[u]+e[i].w;nxt[v][0]=u;nxt[v][1]=i;
if (!bz[v]) q.push(v),bz[v]=1;
}
}
bz[u]=0;
}
return dist[en];
}
inline void dg(int x)
{
if (x>k)
{
cnt=-1;
for (R i=1;i<=n;++i)
head[i]=-1;
for (R i=1;i<=m;++i)
add(bian[i].x,bian[i].y,bian[i].z),add(bian[i].y,bian[i].x,bian[i].z);
int sum=0;
for (R i=1;i<=k;++i)
{
int st=f[i],en=n-f[i]+1,tot=spfa(st,en);
if (tot==inf) return;sum+=tot;int now=en;
while (now!=st)
{
e[nxt[now][1]].w=e[nxt[now][1]^1].w=0;now=nxt[now][0];
}
}
ans=min(sum,ans);
return;
}
for (R i=1;i<=k;++i)
{
if (!change[i])
{
change[i]=1;f[x]=i;dg(x+1);change[i]=0;
}
}
}
int main()
{
read(n);read(m);read(k);ans=inf;
for (R i=1;i<=m;++i)
read(bian[i].x),read(bian[i].y),read(bian[i].z);
dg(1);
if (ans==inf) printf("-1
");else printf("%d
",ans);
return 0;
}