题目连接:https://cn.vjudge.net/problem/HDU-5889

题意就不说了，直接说思路，笨方法就是  先用SPFA 跑出最短路，把最短路建图，由于最小割，就是最大流，所以建好图之后直接dinic 求最大流

平常的最大流可能超时，我是用了边优化，才过的

#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 20005;
int N,M;
int u,v,w;
struct Edge{
	int to,value,rev;
	Edge() {}
	Edge(int a,int b,int c):to(a),value(b),rev(c) {}
};
struct node1{
    int v,next,w;
}edge[MAXN];
vector<Edge> E[MAXN];
int deep[MAXN];
int iter[MAXN],head[MAXN];
int id;
void add(int u,int v,int w){
    edge[id].v=v;
    edge[id].w=w;
    edge[id].next=head[u];
    head[u]=id++;
}
inline void Add(int from,int to,int value){
	E[from].push_back(Edge(to,value,E[to].size()));
	E[to].push_back(Edge(from,0,E[from].size()-1));
}

bool BFS(int root,int target) {
	memset(deep,-1,sizeof deep);
	queue<int> Q;
	deep[root] = 0;
	Q.push(root);
	while(!Q.empty())
	{
		int t = Q.front();
		Q.pop();
		for(int i=0 ; i<E[t].size() ; i++)
		{
			if(E[t][i].value > 0 && deep[E[t][i].to] == -1)
			{
				deep[E[t][i].to] = deep[t] + 1;
				Q.push(E[t][i].to);
			}
		}
	}
	return deep[target] != -1;
}

int DFS(int root,int target,int flow){
	if(root == target)return flow;
	for(int &i=iter[root] ; i<E[root].size() ; i++)
	{
		if(E[root][i].value>0 && deep[E[root][i].to] == deep[root]+1)
		{
			int nowflow = DFS(E[root][i].to,target,min(flow,E[root][i].value));
			if(nowflow > 0)
			{
				E[root][i].value -= nowflow;
				E[E[root][i].to][E[root][i].rev].value += nowflow;
				return nowflow;
			}
		}
	}
	return 0;
}


bool vis1[MAXN];
int cnt[MAXN]; 
bool vis[MAXN];
int dist[MAXN];
void spfa(int s){
    memset(vis,0,sizeof(vis));
    memset(dist,INF,sizeof(dist));
    vis[s]=1;
    dist[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        if(u==N) break;
        for(int i=head[u]; i!=-1; i=edge[i].next){
            int v=edge[i].v;
            if (dist[v]>dist[u]+1){
                dist[v]=dist[u]+1;
                if (!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int Dinic(int root,int target){
	int sumflow = 0;
	while(BFS(root,target))	{
		memset(iter,0,sizeof iter);
		int mid;
		while((mid=DFS(root,target,INF)) > 0)sumflow += mid;
	}
	return sumflow;
}
void init(){
	for (int i = 0; i <= 2000;i++)head[i]=-1;
	id=0;
}
int main(){
 	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&N,&M);
		init();
		for(int i=0 ; i< M ; i++){
			scanf("%d %d %d",&u,&v,&w);
			add(u, v,w);
            add(v, u,w);
		}
		spfa(1);
		for(int i = 1; i <= N; ++i) {
        	for(int j = head[i]; ~j; j = edge[j].next) {
          	  	int v = edge[j].v;
        		if(dist[v] - dist[i] == 1) {
           	     	Add(i, v, edge[j].w);
           	 	}
        	}
    	}
		printf("%d\n",Dinic(1,N));
		for (int i = 0; i <= 2000;i++) E[i].clear();
	}
	return 0;
}