题目链接：http://poj.org/problem?id=2135
题目大意：有n个农场。m条边。你从1-n，再从n-1.不能重复经过同一条边，问最短路是多少。保证有解。

思路：边限制流量为1。求n->T流量限制为2的最小费用可行流。

#include  <map>
#include  <set>
#include  <cmath>
#include  <queue>
#include  <cstdio>
#include  <vector>
#include  <climits>
#include  <cstring>
#include  <cstdlib>
#include  <iostream>
#include  <algorithm>
#define Pair pair<LL,LL>
#define fi first
#define se second
#define LL long long
using namespace std;

const LL maxn=5005;
const LL maxm=2e6+10;
const LL INF=1e9+10;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
using namespace std;

inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

struct node {
    LL u,v,f,w,nxt;
} e[maxm];

struct Cost_flow{

    LL head[maxn],num;
    LL h[maxn], dis[maxn], last[maxn], Pree[maxn];
    LL N;
    void init(LL n){
        N=n; num=2;
        memset(head,-1,sizeof(head));
        memset(h, 0, sizeof(h));
        memset(last, 0, sizeof(last));
        memset(Pree, 0, sizeof(Pree));
    }

    inline void add_e(LL x,LL y,LL f,LL z) {
        e[num].u=x;
        e[num].v=y;
        e[num].f=f;
        e[num].w=z;
        e[num].nxt=head[x];
        head[x]=num++;
    }

    inline void Adde(LL x,LL y,LL f,LL z) {//流量-费用
        add_e(x,y,f,z);
        add_e(y,x,0,-z);
    }

    Pair Dij(LL S, LL T) {
        LL zdl=0,fy=0;
        while(1) {
            priority_queue<Pair>q;
            memset(dis,0xf,sizeof(dis));
            dis[S]=0;
            q.push(make_pair(0,S));
            while(q.size()!=0) {
                Pair p=q.top();
                q.pop();
                if(-p.fi!=dis[p.se])
                    continue;
                if(p.se==T)
                    break;
                for(LL i=head[p.se]; i!=-1; i=e[i].nxt) {
                    LL nowcost=e[i].w+h[p.se]-h[e[i].v];
                    if(e[i].f>0&&dis[e[i].v]>dis[p.se]+nowcost) {
                        dis[e[i].v]=dis[p.se]+nowcost;
                        q.push(make_pair(-dis[e[i].v],e[i].v));
                        last[e[i].v]=p.se;
                        Pree[e[i].v]=i;
                    }
                }
            }
            if(dis[T]>INF)
                break;
            for(LL i=0; i<=N; i++)
                h[i]+=dis[i];

            LL nowflow=INF;

            for(LL now=T; now!=S; now=last[now]) {
                nowflow=min(nowflow,e[Pree[now]].f);
            }
            for(LL now=T; now!=S; now=last[now]) {
                e[Pree[now]].f-=nowflow;
                e[Pree[now]^1].f+=nowflow;
            }
            zdl+=nowflow;
            fy+=nowflow*h[T];
        }
        return make_pair(zdl,fy);
    }
}costflow;

int main() {

    int n, m;
    while(~scanf("%d%d", &n, &m)){
        int x, y, z;
        costflow.init(n+5);
        for(int i=1; i<=m; i++){
            scanf("%d%d%d", &x, &y, &z);
            costflow.Adde(x, y, 1, z);
            costflow.Adde(y, x, 1, z);
        }
        costflow.Adde(n, n+1, 2, 0);
        Pair ans=costflow.Dij(1, n+1);

        printf("%d\n",ans.second);//最大流和费用
    }

    return 0;
}