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

火箭队一共有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

  1 #include <cstdio>  2 #include <cstring>  3    4 template <class T>  5 __inline T max(const T &a, const T &b)  6 {  7     return a > b ? a : b;  8 }  9   10 template <class T> 11 __inline T min(const T &a, const T &b) 12 { 13     return a < b ? a : b; 14 } 15   16 __inline char nextChar(void) 17 { 18     static const int siz = 1 << 20; 19       20     static char buf[siz]; 21     static char *hd = buf + siz; 22     static char *tl = buf + siz; 23       24     if (hd == tl) 25         fread(hd = buf, 1, siz, stdin); 26       27     return *hd++; 28 } 29   30 __inline int nextInt(void) 31 { 32     register int ret = 0; 33     register bool neg = false; 34     register char bit = nextChar(); 35       36     for (; bit < 48; bit = nextChar()) 37         if (bit == ‘-‘)neg = !neg; 38       39     for (; bit > 47; bit = nextChar()) 40         ret = ret * 10 + bit - 48; 41       42     return neg ? -ret : ret; 43 } 44   45 const int inf = 2e9; 46 const int mxn = 155; 47 const int mxm = 1000005; 48   49 int n, m, q; 50   51 int G[mxn][mxn]; 52   53 inline void readGraph(void) 54 { 55     for (int i = 0; i <= n; ++i) 56         for (int j = 0; j <= n; ++j) 57             G[i][j] = i == j ? 0 : inf; 58       59     for (int i = 1; i <= m; ++i) 60     { 61         int x = nextInt(); 62         int y = nextInt(); 63         int w = nextInt(); 64           65         G[x][y] = min(G[x][y], w); 66         G[y][x] = min(G[y][x], w); 67     } 68 } 69   70 inline void preworkFloyd(void) 71 { 72     for (int k = 0; k <= n; ++k) 73         for (int i = 0; i <= n; ++i)if (G[i][k] < inf) 74             for (int j = 0; j <= n; ++j)if (G[k][j] < inf) 75                 if (k < i || k < j)G[i][j] = min(G[i][j], G[i][k] + G[k][j]); 76 } 77   78 int s, t, p; 79 int hd[mxm]; 80 int nt[mxm]; 81 int to[mxm]; 82 int fl[mxm]; 83 int vl[mxm]; 84   85 inline void addEdge(int u, int v, int f, int w) 86 { 87     static int tot = 0; 88       89     nt[tot] = hd[u], to[tot] = v, fl[tot] = f, vl[tot] = +w, hd[u] = tot++; 90     nt[tot] = hd[v], to[tot] = u, fl[tot] = 0, vl[tot] = -w, hd[v] = tot++; 91 } 92   93 int dis[mxm]; 94 int pre[mxm]; 95   96 inline bool spfa(void) 97 { 98     static int que[mxm]; 99     static int inq[mxm];100     static int head, tail;101      102     for (int i = s; i <= t; ++i)103         dis[i] = inf, inq[i] = 0;104      105     dis[que[head = 0] = s] = 0, tail = 1, pre[s] = -1;106      107     while (head != tail)108     {109         int u = que[head++], v; inq[u] = 0;110          111         for (int i = hd[u]; ~i; i = nt[i])112             if (fl[i] && dis[v = to[i]] > dis[u] + vl[i])113             {114                 pre[v] = i ^ 1;115                 dis[v] = dis[u] + vl[i];116                  117                 if (!inq[v])118                     inq[que[tail++] = v] = 1;119             }120     }121      122     return dis[t] < inf;123 }124  125 inline int minCost(void)126 {127     int cost = 0;128      129     while (spfa())130     {131         int flow = inf;132          133         for (int i = pre[t]; ~i; i = pre[to[i]])134             flow = min(flow, fl[i ^ 1]);135          136         for (int i = pre[t]; ~i; i = pre[to[i]])137             fl[i] += flow, fl[i ^ 1] -= flow;138          139         cost += dis[t] * flow;140     }141      142     return cost;143 }144  145 inline void buildNetwork(void)146 {147     memset(hd, -1, sizeof(hd));148      149     s = 0;150     p = 2*n + 1;151     t = 2*n + 2;152      153     addEdge(s, p, q, 0);154      155     for (int i = 1; i <= n; ++i)156         addEdge(s, i, 1, 0), 157         addEdge(i + n, i, 1, 0),158         addEdge(i + n, t, 1, 0),159         addEdge(p, i + n, 1, G[0][i]);160      161     for (int i = 1; i <= n; ++i)162         for (int j = i + 1; j <= n; ++j)163             addEdge(i, j + n, 1, G[i][j]); 164 }165  166 signed main(void)167 {168     n = nextInt();169     m = nextInt();170     q = nextInt();171      172     readGraph();173      174     preworkFloyd();175      176     buildNetwork();177      178     printf("%d\n", minCost());179 }