[2019HDU多校第一场][HDU 6582][E. Path]

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 1e17+7;
const ll M = 100005;
const ll N = 100005;
struct E{
    ll nxt,v,w;
};
E edge[M];
ll dpth[M],head[M];
ll n,m;
ll dis1[M],dis2[M];
ll cnt;
ll vis[M];
void add(ll u,ll v,ll w){
    cnt++;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
void spfa(ll s,ll dd[]){
    memset(vis,0,sizeof(vis));
    for(ll i=0;i<=n;i++)dd[i] = inf;
    queue<ll> q;
    dd[s] = 0; vis[s] = 1; q.push(s);
    while(!q.empty()){
        ll u = q.front(); q.pop(); vis[u] = 0;
        for(ll v,w,i=head[u];i!=-1;i=edge[i].nxt){
            v = edge[i].v; w = dd[u]+edge[i].w;
            if(dd[v]>w){
                dd[v] = w;
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
        
    }
}

//初始化从0开始存边 i^1是i的反向边
void init(){
    cnt=-1;
    for(int i=0;i<=n+1;i++)
    	head[i]=-1;
}
struct Edge
{
    ll from,to,cap,flow;
    Edge(ll u,ll v,ll c,ll f):from(u),to(v),cap(c),flow(f){}
};
struct Dinic
{
    ll s,t;
    vector<Edge>edges;        
    vector<ll> G[10005];      
    bool vis[N];           
    ll d[N];             
    ll cur[N];            
    void init()
    {
       for (ll i=0;i<=n+1;i++)
           G[i].clear(),cur[i]=0,d[i]=0,vis[i]=0;
       edges.clear();
    }
    void AddEdge(ll from,ll to,ll cap)
    {
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));       
        ll mm=edges.size();
        G[from].push_back(mm-2);
        G[to].push_back(mm-1);
    }
    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<ll>q;
        q.push(s);
        d[s]=0;
        vis[s]=1;
        while (!q.empty())
        {
            ll x = q.front();q.pop();
            for (ll i = 0;i<G[x].size();i++)
            {
                Edge &e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to]=1;
                    d[e.to] = d[x]+1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    ll DFS(ll x,ll a)
    {
        if (x==t || a==0)
            return a;
        ll flow = 0,f;
        for(ll &i=cur[x];i<G[x].size();i++)
        {
            Edge &e = edges[G[x][i]];
            if (d[x]+1 == d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0)
            {
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if (a==0)
                    break;
            }
        }
        return flow;
    }
    ll Maxflow(ll s,ll t)
    {
        this->s=s;
        this->t=t;
        ll flow = 0;
        while (BFS())
        {
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,inf);
        }
        return flow;
    }
}dc;

ll a[M],b[M],c[M];
int main(){
    ll T,x,y,z;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld %lld",&n,&m);
        init();
        for(ll i=1;i<=m;i++){
            scanf("%lld %lld %lld",&x,&y,&z);
            a[i] = x;    b[i] = y;    c[i] = z;
            add(x,y,z);
        } 
        dc.s = 1; dc.t = n;
        spfa(1,dis1);    
        
        cnt = -1;
        for(ll i=0;i<=n+1;i++)head[i] = -1;
        
        for(ll i=1;i<=m;i++){
            x = a[i];    y = b[i];    z = c[i];
            add(y,x,z);    
        }
        
        spfa(n,dis2);
        
		dc.init();
        
        for(ll i=1;i<=m;i++){
            if(a[i]!=b[i]&&dis1[a[i]]+c[i]+dis2[b[i]]==dis1[n]){
                dc.AddEdge(a[i],b[i],c[i]);  
            }
        }
        cout<<dc.Maxflow(1,n)<<endl;
    }
    return 0;
}