题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6582

题目大意：有n个点,m条单向带权边，起点为1，终点为n，如果开始没有最短路输出0,现在想堵住一些路，使堵之后的最短路值变大，或不存在。堵路的花费就是边的权值，问最小花费。

思路：找到最短路核心边，再重新建边，跑一遍最小割即可。找最短路核心边要正向建边找每点到起点的距离（假设为d[i]），再反向建边找每点到终点的距离(假设为d2[i])，如果一条边起点为u,终点为v，边权为w,若d[u]+d2[v]+w==d[n]则这是一条最短路核心边。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL maxn=10005;
const LL INF=10000000000000000;
LL d[maxn], cur[maxn], start, tend;
struct node
{
    LL to, cap, next;
} edge[maxn << 1];
LL head[maxn];

LL cnt;
void addedge(LL start, LL to, LL cap)
{
    edge[cnt].to = to;
    edge[cnt].cap = cap;
    edge[cnt].next = head[start];
    head[start] = cnt++;
}
bool BFS()
{
    //memset(vis,false,sizeof(vis));
    memset(d, -1, sizeof(d));
    LL Q[maxn * 2];
    LL Thead, Ttail;
    Thead = Ttail = 0;
    Q[Ttail++] = start;;
    d[start] = 0;
    //vis[start]=1;
    while (Thead<Ttail)
    {
        LL x = Q[Thead];
        if (x == tend)
            return true;
        for (LL i = head[x]; i != -1; i = edge[i].next)
        {
            LL temp = edge[i].to;
            if (d[temp] == -1 && edge[i].cap>0)//没有标记,且可行流大于0
            {
                //vis[temp.to]=true;
                d[temp] = d[x] + 1;
                Q[Ttail++] = temp;
            }
        }
        Thead++;
    }
    return false;//汇点是否成功标号,也就是说是否找到增广路
}
LL DFS(LL x, LL cap)
{
    if (x == tend)
        return cap;
    //vis[start]=true;
    LL flow = 0, f;
    for (LL i = head[x]; i != -1; i = edge[i].next)
    {
        LL temp = edge[i].to;
        //if(temp.cap<=0||vis[temp.to])continue;
        if (d[temp] == d[x] + 1 && edge[i].cap)
        {
            f = DFS(temp, min(cap - flow, edge[i].cap));
            edge[i].cap -= f;
            edge[i ^ 1].cap += f;
            flow += f;
            if (flow == cap)
                break;
        }
    }
    if (!flow)
        d[x] = -2;//防止重搜
    return flow;
}
LL maxflow()
{
    LL flow = 0, f;
    while (BFS())
    {
        //memset(vis,false,sizeof(vis));
        while ((f = DFS(start, INF))>0)
            flow += f;
    }
    return flow;
}

vector< pair<LL ,LL > > e1[maxn], e2[maxn];
LL n, m;
LL dis[maxn];   //dis当前的最短路
LL vis[maxn];   //是否已经求出最短路
LL dis2[maxn];   //dis当前的最短路
LL vis2[maxn];   //是否已经求出最短路
LL xx[maxn], yy[maxn], zz[maxn];

priority_queue<pair<LL, LL> > q;
LL dijkstra(LL s, LL t)
{
    while(!q.empty())
    {
        q.pop();
    }
    dis[s]=0;
    q.push(make_pair(-dis[s], s));
    while(!q.empty())
    {
        LL now=q.top().second;                //一定是最短路上的顶点
        q.pop();
        if(vis[now])
        {
            continue;
        }
        vis[now]=1;
        for(LL i=0;i<e1[now].size();i++)       //访问所有的邻接点
        {
            LL v=e1[now][i].first;
            if(!vis[v]&&dis[v]>dis[now]+e1[now][i].second)
            {
                dis[v]=dis[now]+e1[now][i].second;
                q.push(make_pair(-dis[v], v));//把可能的最短路顶点加入队列
            }
        }
    }
    if(dis[t]==INF)
    {
        return -1;                            //s-t没有通路
    }
    else
    {
        return dis[t];
    }

}

LL dijkstra2(LL s, LL t)
{
    memset(vis, 0 ,sizeof(vis));
    while(!q.empty())
    {
        q.pop();
    }
    dis2[s]=0;
    q.push(make_pair(-dis2[s], s));
    while(!q.empty())
    {
        LL now=q.top().second;                //一定是最短路上的顶点
        q.pop();
        if(vis[now])
        {
            continue;
        }
        vis[now]=1;
        for(LL i=0;i<e2[now].size();i++)       //访问所有的邻接点
        {
            LL v=e2[now][i].first;
            if(!vis[v]&&dis2[v]>dis2[now]+e2[now][i].second)
            {
                dis2[v]=dis2[now]+e2[now][i].second;
                q.push(make_pair(-dis2[v], v));//把可能的最短路顶点加入队列
            }
        }
    }
    if(dis2[t]==INF)
    {
        return -1;                            //s-t没有通路
    }
    else
    {
        return dis2[t];
    }

}

int main()
{
    LL t;
    scanf("%lld",&t);
    while(t--)
    {
        LL n, m;
        scanf("%lld%lld",&n,&m);
        for(LL i=0;i<maxn;i++)   //初始化
        {
            vis[i]=0;
            dis[i]=INF;
            dis2[i]=INF;
            e1[i].clear();
            e2[i].clear();
        }

        for(LL i=0;i<m;i++)
        {
            LL x, y, z;
            scanf("%lld%lld%lld",&x,&y,&z);
            xx[i]=x, yy[i]=y, zz[i]=z;
            e1[x].push_back(make_pair(y ,z));
            e2[y].push_back(make_pair(x ,z));
        }

        dijkstra(1, n);
        dijkstra2(n, 1);

        cnt = 0;
        memset(head, -1, sizeof(head));

        start=1;
        tend=n;

        for(LL i=0; i<=m; i++)
        {
            LL u=xx[i], v=yy[i], w=zz[i];
            if(dis[u]+dis2[v]+w==dis[n])
            {
                addedge(u, v, w);
                addedge(v, u, 0);
            }
        }
        cout<<maxflow()<<endl;

    }
    return 0;
}