旅行(travel)
从前有一位旅者，他想要游遍天下所有的景点。这一天他来到了一个神奇的王国：在这片土地上，有n个城市，从1到n进行编号。王国中有m条道路，第i条道路连接着两个城市ai,bi，由于年代久远，所有的道路都已经不能使用。如果要修复第i条道路，需要wi的时间。为了更好的旅行，旅者想要将某些道路修复，使得1号城市能够到达n号城市，2号城市能够到达n-1号城市..k号城市能够到达n-k+1号城市。为了满足他的要求，请问最少需要多少时间去修复道路。无解请输出-1。
输入格式：
第一行：n,m,k
接下来m行：ai,bi,wi
含义如上所述。
输出格式：
输出共一行：最少需要多少时间修复道路。如果始终无法满足旅者的要求，请输出-1。
样例输入：
5 5 2 1 3 4 3 5 2 2 3 1 3 4 4 2 4 3
样例输出：
9
数据范围：
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
时间限制：
3000
咋一看本题突然就想到要用生成树，然后仔细观察，发现这个k小得莫名其妙，于是弄出了一个暴枚+SPFA的算法，枚举每组i到n-k+i的顺序，再把最短路长度全部清零，取每种排列的最小值。
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
;
struct node{
int from,to,next,dis,bro;
}edge[N*];
,dis[N],ans=,last[N];
],in[N],can=true;
inline void unite(int x,int y,int w,int b)
{
edge[s].from=x;
edge[s].bro=b;
edge[s].to=y;
edge[s].dis=w;
edge[s].next=head[x];
head[x]=s;
return;
}
inline ;return;}
inline void dfs(int step,int res)
{
if(step==k)
{
ans=min(ans,res);
return;
}
if(!can) return;
node store[N*];
;i<=s;i++) store[i]=edge[i];
;
;u<=k;u++) )
{
used[u]=;
) ;i<=s;i++) edge[i]=store[i];
;
queue<int> Q;
memset(dis,,sizeof(dis));
memset(last,,sizeof(last));
];
dis[u]=;
Q.push(u);
while(!Q.empty())
{
int f=Q.front();
Q.pop();
;
for(int i=head[f];i;i=edge[i].next) if(edge[i].dis+dis[f]<dis[edge[i].to])
{
dis[edge[i].to]=edge[i].dis+dis[f];
last[edge[i].to]=i;
if(!in[edge[i].to])
{
Q.push(edge[i].to);
;
}
}
}
]) can=;
else
{
;
)
{
del(last[p]);
del(edge[last[p]].bro);
p=edge[last[p]].from;
}
dfs(step+,res+dis[n-u+]);
}
used[u]=;
}
return;
}
int main()
{
int x,y,w;
scanf("%d%d%d",&n,&m,&k);
;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
s++;unite(x,y,w,s+);
s++;unite(y,x,w,s-);
}
memset(used,,sizeof(used));
dfs(,);
if(!can) printf("-1\n");
else printf("%d\n",ans);
;
}