大家都很强， 可与之共勉。
震惊！cky 竟率兵攻打jyb！
jyb 面对强敌，振作精神，想要抗击侵略。jyb 的国家一共有n 个城市，m 条距离为1 的双向道路。现在jyb的所在地是1 号城市，cky 已经占领了n 号城市。jyb 得到线报，cky 想要走最近的路线抓到自己，而jyb 还在调集部队，所以他希望拖延一点时间。他派出了一些工程人员去破坏道路，破坏每条道路都要消耗一定的资源，jyb 希望消耗最小的资源并且保证能拖延到cky。
Input
第1 行，1 个整数T, 表示数据组数，对于每组数据：
第1 行，2 个整数n;m，表示城市数和道路数
接下来m 行，每行3 个整数u; v;w, 表示城市u 到城市v 有一条路，破坏消耗的资源为w。
Output
对于每组数据，输出最小消耗的资源。
Sample
roadblock.in
1
4 4
1 2 1
2 4 2
3 1 3
4 3 4
roadblock.out
4
数据范围:
1 T 5, 1 n 1000，1 m 10000，1 w 300000。
题意其实挺简单的，先BFS找出最短路，因为边权为1，最短路显然有很多，然后我们建一个只有最短路上边的新图，然后跑出最小割就好。需要加当前弧优化才能过所有点。
调了我好久啊， 天哪！
#include "queue"
#include "cctype"
#include "cstdio"
#include "cstring"
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define rep(i, m, n) for(register int i = (m); i <= (n); ++i)
#define edges(u) for(register int i = head[u]; i; i = g[i].pre)
template <class T>
inline bool readIn(T &x) {
T opt = 1;
static char ch;
while(!isdigit(ch = (char) getchar()) && (ch ^ -1) && (ch ^ 45));
if(ch == -1) return false;
if(ch == 45) opt = -1, ungetc(ch, stdin);
for(x = -48 + ch; isdigit(ch = (char) getchar()); x = (x << 1) + (x << 3) + ch - 48);
x *= opt;
return true;
}
template <class T>
inline bool writeIn(T x) {
T st[25], top = 0;
if(x < 0) putchar('-'), x = -x;
if(x == 0) { putchar(48); return true; }
while(x) st[++top] = x % 10, x /= 10;
while(top) putchar(st[top--] + 48);
return true;
}
const int oo = 0x3f3f3f3f;
struct edge {
int to, pre, cost;
edge(int to = 0, int pre = 0, int cost = 0) : to(to), pre(pre), cost(cost) { }
} g[20005];
struct Edge {
int to, cap, flow, pre;
Edge(int to = 0, int flow = 0, int cap = 0, int pre = 0) : to(to), flow(flow), cap(cap), pre(pre) { }
} e[20005];
typedef long long LL;
int T, n, m, tot, ne, head[10005], dis1[10005], dis2[10005], u[10005], v[10005], w[10005];
LL ans;
void SPFA(int s, int t) {
static std::deque<int> q;
static bool vis[10005];
memset(dis1, 0x3f, sizeof (int) * (n + 1));
memset(dis2, 0x3f, sizeof (int) * (n + 1));
memset(vis, false, sizeof (int) * (n + 1));
q.push_front(s); vis[s] = true; dis1[s] = 0;
while( !q.empty() ) {
int u = q.front(); q.pop_front();
vis[u] = false;
edges(u) {
int v = g[i].to;
if( dis1[v] > dis1[u] + 1 ) {
dis1[v] = dis1[u] + 1;
if( !vis[v] ) {
if( q.empty() || dis1[v] < dis1[q.front()] )
q.push_front(v);
else
q.push_back(v);
vis[v] = true;
}
}
}
}
memset(vis, false, sizeof (int) * (n + 1));
q.push_front(t); vis[t] = true; dis2[t] = 0;
while( !q.empty() ) {
int u = q.front(); q.pop_front();
vis[u] = false;
edges(u) {
int v = g[i].to;
if( dis2[v] > dis2[u] + 1 ) {
dis2[v] = dis2[u] + 1;
if( !vis[v] ) {
if( q.empty() || dis2[v] < dis2[q.front()] )
q.push_front(v);
else
q.push_back(v);
vis[v] = true;
}
}
}
}
}
class Dinic {
public:
int d[10005], cur[10005], s, t;
std::queue<int> Q;
bool vis[10005];
bool bfs(int s, int t) {
memset(vis, false, sizeof (int) * (n + 1));
d[s] = 0, vis[s] = true;
Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for( int i = head[u]; i; i = e[i].pre ) {
int v = e[i].to;
if( !vis[v] && e[i].cap > e[i].flow ) {
vis[v] = true;
d[v] = d[u] + 1;
Q.push(v);
}
}
}
return vis[t];
}
int dfs( int u, int a ) {
if( u == t || !a ) return a;
int flow = 0, f;
for(register int &i = cur[u]; i; i = e[i].pre ) {
int v = e[i].to;
if( d[u] + 1 == d[v] && (f = dfs(v, min(e[i].cap - e[i].flow, a))) > 0) {
e[i].flow += f;
e[i^1].flow -= f;
flow += f;
a -= f;
if(!a) return flow;
}
}
return flow;
}
int Maxflow( int s, int t ) {
this->s = s, this->t = t;
int flow = 0;
while( bfs( s, t ) ) {
rep(i, 1, n) cur[i] = head[i];
flow += dfs( s, oo );
}
return flow;
}
} M;
#define adde(u, v, cost) { g[++ne] = edge(v, head[u], cost); head[u] = ne; }
inline void initialize() {
readIn(n);readIn(m); ne = 1, tot = 0;
memset(head, 0, sizeof (int) * (n + 1));
int x, y, o;
while( m-- ) {
readIn(x);readIn(y);readIn(o);
adde(x, y, o);adde(y, x, o);
}
SPFA(1, n);
rep(x, 1, n) edges(x) if(dis1[x] + dis2[g[i].to] + 1 == dis1[n]) { u[++tot] = x, v[tot] = g[i].to, w[tot] = g[i].cost; }
ne = 1;
memset(head, 0, sizeof (int) * (n + 1));
rep(i, 1, tot) {
e[++ne] = Edge(v[i], 0, w[i], head[u[i]]); head[u[i]] = ne;
e[++ne] = Edge(u[i], 0, 0, head[v[i]]); head[v[i]] = ne;
}
}
int main() {
freopen("roadblock.in", "r", stdin);
freopen("roadblock.out", "w", stdout);
for(readIn(T); T; --T) {
initialize();
writeIn(M.Maxflow(1, n));
putchar(10);
}
}