description
从前有一位旅者，他想要游遍天下所有的景点。这一天他来到了一个神奇的王国：在这片土地上，有n个城市，从1到n进行编号。王国中有m条道路，第i条道路连接着两个城市ai,bi，由于年代久远，所有的道路都已经不能使用。如果要修复第i条道路，需要wi的时间。为了更好的旅行，旅者想要将某些道路修复，使得1号城市能够到达n号城市，2号城市能够到达n-1号城市..k号城市能够到达n-k+1号城市。为了满足他的要求，请问最少需要多少时间去修复道路。无解请输出-1。
analysis
可以\(O(4!)\)暴力枚举这\(k\)组关系的顺序
然后依次跑\(SPFA\)，每跑一次把最短路上的边权标零，记录最小值即可
听着是不是没有问题？其实这是水法，连拍都过不了233
正解斯坦纳树，我还不会
code
#pragma GCC optimize("O3")#pragma G++ optimize("O3")#include #include #include #include #define MAXN 10005#define MAXM 20005#define INF 1000000007#define ll long long#define reg register ll#define fo(i,a,b) for (reg i=a;i<=b;++i)#define fd(i,a,b) for (reg i=a;i>=b;--i)#define rep(i,a) for (reg i=last[a];i;i=next[i])using namespace std;ll last[MAXM],next[MAXM],tov[MAXM],len[MAXM];ll f[5],pre[MAXN][2],dis[MAXN];bool bo[5],bz[MAXN];ll n,m,k,tot,ans=INF;deque q;struct edge{ ll x,y,z; }a[MAXN];inline ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0' || '9' k) { ll cnt=0; memset(last,0,sizeof(last)),memset(next,0,sizeof(next)), memset(tov,0,sizeof(tov)),memset(len,0,sizeof(len)),tot=1; fo(i,1,m)link(a[i].x,a[i].y,a[i].z),link(a[i].y,a[i].x,a[i].z); fo(i,1,k) { ll beg=f[i],end=n-f[i]+1,pos=end; ll tmp=spfa(beg,end); if (tmp>=INF)return;cnt+=tmp; while (pos!=beg)len[pre[pos][1]]=len[pre[pos][1]^1]=0,pos=pre[pos][0]; } ans=min(ans,cnt); return; } fo(i,1,k)if (bo[i])bo[i]=0,f[x]=i,dfs(x+1),bo[i]=1;}int main(){ n=read(),m=read(),k=read(); fo(i,1,m)a[i].x=read(),a[i].y=read(),a[i].z=read(); memset(bo,1,sizeof(bo)),dfs(1); if (ans