http://acm.hdu.edu.cn/showproblem.php?pid=6582

思路：找到最短路核心边建图，跑一遍最小割，最短路核心边的定义为设起点到每个点的最短距离为d[i]，每个点到终点的最短路为d2[i]，如果一条边起点为u,终点为v，边权为w,若d[u]+d2[v]+w==d[n]则这是一条最短路核心边。所以先用spfa求d[i],然后反向spfa求d2[i]，最后建图dinic求出答案。

#include
#include
#include
#include

void add(int u,int v,ll w)//正向建边
{
e[cnt].u=u,e[cnt].v=v,e[cnt].w=w;
e[cnt].nxt=h[u];h[u]=cnt++;
}

void add2(int u,int v,ll w)//反向建边
{
e2[cnt2].u=u,e2[cnt2].v=v,e2[cnt2].w=w;
e2[cnt2].nxt=h2[u],h2[u]=cnt2++;
}
void add3(int u,int v,ll w)//重新建边
{
e3[cnt3].u=u,e3[cnt3].v=v,e3[cnt3].w=w;
e3[cnt3].nxt=h3[u],h3[u]=cnt3++;
}

bool spfa()//求每点到1的最短距离
{
queue q;
memset(vis,,sizeof(vis));
d[st]=;
vis[st]=;
q.push(st);
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=;
for(int i=h[u];i!=-;i=e[i].nxt)
{
int v=e[i].v;
ll w=e[i].w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
if(!vis[v])
{
vis[v]=;
q.push(v);
}
}
}
}
return d[n]==inf;
}

void re_spfa()//求每点到n的最短距离
{
queue q;
memset(vis,,sizeof(vis));
d2[ed]=;
vis[ed]=;
q.push(ed);
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=;
for(int i=h2[u];i!=-;i=e2[i].nxt)
{
int v=e2[i].v;
ll w=e2[i].w;
if(d2[v]>d2[u]+w)
{
d2[v]=d2[u]+w;
if(!vis[v])
{
vis[v]=;
q.push(v);
}
}
}
}
}

void create_map()//重新建边
{
for(int i=;i<cnt;i++)
{
int u=e[i].u;
int v=e[i].v;
ll w=e[i].w;
if((d[u]+d2[v]+w==d[ed])&&(d[u]<inf&&d2[v]<inf))
{//最短路核心边
add3(u,v,w);
add3(v,u,);
}
}
}

bool bfs(){//dinic分层
queue que;
memset(depth,,sizeof(depth));
que.push(st);
depth[st]=;
while(!que.empty()){
int u=que.front();
que.pop();
if(u==ed)
return true;
for(int i=h3[u];i!=-;i=e3[i].nxt){
int v=e3[i].v;
ll w=e3[i].w;
if(!depth[v]&&w){
depth[v]=depth[u]+;
que.push(v);
}
}
}
return false;
}

ll dfs(int u,ll dis)
{
if(u==ed)
return dis;
ll res=;
for(int i=h3[u];i!=-;i=e3[i].nxt)
{
int v=e3[i].v;
ll w=e3[i].w;
if((depth[v]==depth[u]+)&&w)
{
ll di=dfs(v,min(w,dis-res));
e3[i].w-=di;
e3[i^].w+=di;
res+=di;
if(res==dis)
return dis;
}
}
return res;
}

void dinic()//dinic求最小割
{
ll ans=;
while(bfs())
{
ans+=dfs(st,inf);
}
printf("%lld\n",ans);
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
st=,ed=n;
init();
for(int i=;i<m;i++)
{
int u,v;ll w;
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
add2(v,u,w);
}
if(spfa())//特判，没有最短路
printf("0\n");
else
{
re_spfa();
create_map();
dinic();
}
}
return ;
}