Description：

给一个图，选 $k$ 条从 $0$ 开始的路径覆盖整个图。

$1\leqslant n\leqslant 150,1\leqslant m\leqslant 20000$

Solution：

拆点之后就是一个有源汇有上下界最小费用可行流，可以先用 $floyed$ 预处理 $d[i][j]$ 表示在只经过不大于 $i,j$ 的点的情况下从 $i$ 到 $j$ 的最短距离，然后按有上下界可行流的方式连边跑最小费用最大流即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 400

#define MAXM 60010

struct edge

{

	int to,nxt,f,c;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b,int f,int c)

{

	e[edgenum] = (edge){b,lin[a],f,c};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-c};lin[b] = edgenum++;

	return;

}

int pre[MAXN],d[MAXN],rate[MAXN];

bool inq[MAXN];

int s,ss,t,tt;

#define INF 0x3f3f3f3f

bool SPFA()

{

	queue<int> q;q.push(s);

	memset(d,0x3f,sizeof(d));d[s] = 0;

	rate[s] = INF;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!inq[e[i].to])

				{

					inq[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return d[t] != INF;

}

int flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return rate[t] * d[t];

}

int EK()

{

	int ans = 0;

	while(SPFA())ans += flow();

	return ans;

}

int dis[MAXN][MAXN];

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d%d",&n,&m,&k);

	int a,b,c;

	memset(dis,0x3f,sizeof(dis));

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		dis[a][b] = dis[b][a] = min(dis[a][b],c);

	}

	for(int i = 0;i <= n;++i)dis[i][i] = 0;

	for(int k = 0;k <= n;++k)

		for(int i = 0;i <= n;++i)

			for(int j = 0;j <= n;++j)

				if(k < max(i,j))dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);

	s = 2 * n + 1;t = s + 1;

	for(int i = 1;i <= n;++i)add(0,2 * i - 1,1,dis[0][i]);

	for(int i = 1;i <= n;++i)add(s,2 * i,1,0);

	for(int i = 1;i <= n;++i)add(2 * i - 1,t,1,0);

	add(s,0,k,0);

	for(int i = 1;i <= n;++i)

		for(int j = i + 1;j <= n;++j)

			add(2 * i,2 * j - 1,1,dis[i][j]);

	cout << EK() << endl;

	return 0;

}