Description

【题意】
约翰家有 $N$ 间牛棚，M条双向道路连接了这些牛棚，第 $i$ 条道路连接了第 $A_i$ 间牛棚和第 $B_i$ 间牛棚，长度为 $L_i$ 。
所有牛棚中最好的是第一间和最后一间，所以当有朋友来访时，他会带着朋友从第一间牛棚走到第 $N$ 间牛棚，然后再回到第一间牛棚。
约翰想让朋友多看看乡村不同的景色，所以希望来回的路上不重复经过任何一条道路，不过重复经过一间牛棚是允许的。
请帮助约翰选择一条路线，使得往返路径的总长度最短。输入数据保证路线总是存在的。

【输入格式】
第一行：两个整数 $N$ 和 $M$，$1 \le N \le 1000,1 \le M \le 10000$
第二行到第 $M+1$ 行：第 $i+1$ 行有三个整数 $A_i$，$B_i$ 和 $L_i$ ，$1 \le A_i,B_i \le N$,$1 \le L_i \le 35000$

【输出格式】
单个整数，表示最短路线的总长度。

【样例输入】
4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

【样例输出】
6

【解释】
1→2→4→3→1

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=1100,M=50000;
struct edge{int x,y,f,c,pre;}a[M];int alen,last[N],cur[N];
void ins(int x,int y,int f,int c)
{
    a[++alen]={x,y,f,c,last[x]};last[x]=alen;
    a[++alen]={y,x,0,-c,last[y]};last[y]=alen;
}
int n,m,st,ed,d[N];bool v[N];
bool spfa()
{
    queue<int> q;
    memset(d,0x0f,sizeof(d));d[st]=0;
    memset(v,0,sizeof(v));
    q.push(st);v[st]=1;
    while(!q.empty())
	{
        int x=q.front();q.pop();v[x]=0;
        for(int k=last[x];k;k=a[k].pre)if(a[k].f)
		{
            int y=a[k].y;
            if(d[y]>d[x]+a[k].c)
			{
                d[y]=d[x]+a[k].c;
                if(!v[y])q.push(y),v[y]=1;
            }
        }    
    }
    return d[ed]!=d[0];
}
int ans;
int dinic(int x,int f)
{
    if(x==ed) return ans+=d[ed]*f,f;
    int sx=0;
    v[x]=1;
    for(int k=cur[x];k;k=a[k].pre)if(a[k].f)
	{
        cur[x]=k;
        int y=a[k].y;if(v[y])continue;
        if(d[y]==a[k].c+d[x])
		{
            int sy=dinic(y,min(f-sx,a[k].f));
            a[k].f-=sy,a[k^1].f+=sy;
            sx+=sy;if(sx==f) return f;
        }
    }
    if(sx>0)v[x]=0;
    return sx;
}
int main()
{
scanf("%d%d",&n,&m);
alen=1;memset(last,0,sizeof(last));
for(int i=1;i<=m;i++)
{
int x,y,c,f;scanf("%d%d%d",&x,&y,&c);
ins(x,y,1,c);ins(y,x,1,c);
}
st=n+1,ed=n+2;
ins(st,1,2,0);
ins(n,ed,2,0);
ans=0;
while(spfa())
{
memcpy(cur,last,sizeof(cur));
int t=dinic(st,1<<30);
}
printf("%d\n",ans);
return 0;
}

</p>