皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。

火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。

由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧毁1到K-1号据点，并且，如果K-1号据点没有被摧毁，由于防御的连锁性，小智一行任何一个人进入据点K，都会被发现，并产生严重后果。因此，在K-1号据点被摧毁之前，任何人是不能够经过K号据点的。

为了简化问题，我们忽略战斗环节，小智一行任何一个人经过K号据点即认为K号据点被摧毁。被摧毁的据点依然是可以被经过的。

K个人是可以分头行动的，只要有任何一个人在K-1号据点被摧毁之后，经过K号据点，K号据点就被摧毁了。显然的，只要N号据点被摧毁，皮卡丘就得救了。

野外的道路是不安全的，因此小智一行希望在摧毁N号据点救出皮卡丘的同时，使得K个人所经过的道路的长度总和最少。

请你帮助小智设计一个最佳的营救方案吧！

第一行包含三个正整数N，M，K。表示一共有N+1个据点，分别从0到N编号，以及M条无向边。一开始小智一行共K个人均位于0号点。 

接下来M行，每行三个非负整数，第i行的整数为Ai，Bi，Li。表示存在一条从Ai号据点到Bi号据点的长度为Li的道路。

仅包含一个整数S，为营救皮卡丘所需要经过的最小的道路总和。

对于100%的数据满足N ≤ 150, M ≤ 20 000, 1 ≤ K ≤ 10, Li ≤ 10 000, 保证小智一行一定能够救出皮卡丘。至于为什么K ≤ 10，你可以认为最终在小智的号召下，小智，小霞，小刚，小建，小遥，小胜，小光，艾莉丝，天桐，还有去日本旅游的黑猫警长，一同前去大战火箭队。

Day2

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<queue>//by NeighThorn#define inf 0x3f3f3f3fusing namespace std;   const int maxn=500+5,maxm=500000+5;   int n,m,K,S,T,cnt,w[maxm],d[maxn][maxn],fl[maxm],hd[maxn],to[maxm],nxt[maxm],dis[maxn],vis[maxn],Min[maxn],from[maxn];   inline bool spfa(void){    memset(dis,inf,sizeof(dis));    memset(Min,inf,sizeof(Min));    queue<int> q;q.push(S),vis[S]=1,dis[S]=0;    while(!q.empty()){        int top=q.front();q.pop(),vis[top]=0;        for(int i=hd[top];i!=-1;i=nxt[i]){            if(dis[to[i]]>dis[top]+w[i]&&fl[i]){                from[to[i]]=i;                dis[to[i]]=dis[top]+w[i];                Min[to[i]]=min(Min[top],fl[i]);                if(!vis[to[i]])                    vis[to[i]]=1,q.push(to[i]);            }        }    }    return dis[T]!=inf;}    inline int find(void){    for(int i=T;i!=S;i=to[from[i]^1])        fl[from[i]]-=Min[T],fl[from[i]^1]+=Min[T];    return dis[T]*Min[T];}       inline int mcmf(void){    int res=0;    while(spfa())        res+=find();    return res;}    inline void add(int l,int s,int x,int y){    w[cnt]=l;fl[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;    w[cnt]=-l;fl[cnt]=0;to[cnt]=x;nxt[cnt]=hd[y];hd[y]=cnt++;}   signed main(void){    memset(d,inf,sizeof(d));    memset(hd,-1,sizeof(hd));cnt=0;    scanf("%d%d%d",&n,&m,&K);S=2*n+1,T=n*2+2;    for(int i=0;i<=n;i++)        d[i][i]=0;    for(int i=1,s,x,y;i<=m;i++)        scanf("%d%d%d",&x,&y,&s),d[x][y]=d[y][x]=min(d[x][y],s);    for(int k=0;k<=n;k++)        for(int i=0;i<=n;i++)            for(int j=0;j<=n;j++)                if(k<=i||k<=j)                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);    add(0,K,S,0);    for(int i=1;i<=n;i++)        add(0,1,S,i);    for(int i=1;i<=n;i++)        add(0,1,i+n,T);    for(int i=0;i<n;i++)        for(int j=i+1;j<=n;j++)            add(d[i][j],1,i,j+n);    printf("%d\n",mcmf());    return 0;}//Cap ou pas cap. Cap.