> 百度里有很多大牛对这道题写了博客，但代码里没解释，我花了好几天才弄懂了这算法，现写下来给各位fish作参考，可更容易明白。
> /*poj2135 */
> #include<stdio.h>
> #include<iostream>
> #include<string>
> #include<queue>
> #include<vector>
> #define M 10002
> #define inf 1<<30
> using namespace std;
> struct Edge{
>     int u,v;
>     int c,f;
>     int next;
>  }edge[4*M];
>  int pre[1002],p[1002];  //pre[]的用处在构造邻接边中，p[]记录路线
>  int tot,n,m;
>  int dist[1002],vist[1002];//用在spfa中，分别为：记录源点0到各点的最短距离(即费用),访问标记
>  void add(int u,int v,int c,int f)
>  {
>     Edge e = {u,v,c,f,pre[u]}; //pre[u]是记录前一条edge中：开始点为u的边的值
>     edge[tot] = e;
>     pre[u] = tot++;   //更新pre[u]=tot ,tot++
> }
> void addedge2(int u,int v,int c,int f)
> {
>     add(u ,v ,c ,f); //正向的边，
>     add(v,u,-c,0);  //对应的反向边，费用为-c,流量为0
> }
>  bool spfa()    //寻找费用最小的可增广路,spfa算法
>  {
>     int u,v;
>     queue<int>que;
>     memset(p,-1,sizeof(p));
>     memset(vist,0,sizeof(vist));
>     fill(&dist[0],&dist[1002],inf);//不能用 memset(dist,inf,sizeof(dist));或用for等
>     vist[0]=1;dist[0]=0;
>     que.push(0);
>     while(!que.empty()){
>         u=que.front();que.pop();vist[u]=0;//取出队头元素
>         for(int i=pre[u];i!=-1;i=edge[i].next){ //与u相接的所有边
>             if(edge[i].f){     //有流量
>                 v=edge[i].v;
>                 if(dist[v]>dist[u]+edge[i].c){  //调整
>                   dist[v]=dist[u]+edge[i].c;
>                   p[v]=i;//记录路线
>                   if(!vist[v]){que.push(v); vist[v]=1;}//入队
>                 }
>             }
>         }
>     }
>     return dist[n+1]!=inf;
>  }
>  int cost()   //因这题路的流量为1，不用求流量了
>  {
>     int ans=0,x;
>     while(spfa()){
>         ans+=dist[n+1];
>         x=p[n+1];
>         while(x!=-1){
>             edge[x].f-=1;  //正边
>             edge[x^1].f+=1;  //反边
>             x=p[edge[x].u];  //x变为连接到 edge[x].u的边
>         }
>     }
>     return ans;
>  }
>  int main()
>  {
>     int i,a,b,c;
>     scanf("%d %d",&n,&m);
>     memset(pre,-1,sizeof(pre)); tot=0;
>     addedge2(0,1,0,2);       //增加源点0，汇点n+1,
>     addedge2(n,n+1,0,2);
>     for(i=0;i<m;i++){
>         scanf("%d %d %d",&a,&b,&c);
>         addedge2(a,b,c,1);
>         addedge2(b,a,c,1);
>     }
>     printf("%d\n",cost());
>     return 0;
>  }
> 
> 
> /* void addedge2(int u,int v,int c,int f)
>  {
>     Edge e = {u,v,c,f,pre[u]};
>     edge[tot]=e; //正向的边，pre[u]是记录前一条edge中：开始点为u的边的值
>     pre[u]=tot++;       //更新pre[u]=tot ,tot++
>     Edge e = {v,u,-c,0,pre[v]};
>     edge[tot]=e;  //对应的反向边，费用为-c,流量为0
>     pre[v]=tot++;
>  }   */ //这有语法错误  948K 63MS