题目链接：

思路：把路长看作费用，然后如果u,v之间有边，就连u->v,v->u,边容量为1,表示每条边只能走一次，最后就是源点与1连边，容量为2，费用为0，n与汇点连边，容量为2，费用为0，表示增广2次。这样就转化为为最小费用最大流问题来求解了。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 #define MAXN 1010  8 #define MAXM 88888  9 #define inf 1<<30 10  11 struct Edge{ 12     int v,cap,cost,next; 13 }edge[MAXM]; 14  15 int n,m,NE,vs,vt; 16 int head[MAXN]; 17  18 void Insert(int u,int v,int cap,int cost) 19 { 20     edge[NE].v=v; 21     edge[NE].cap=cap; 22     edge[NE].cost=cost; 23     edge[NE].next=head[u]; 24     head[u]=NE++; 25  26     edge[NE].v=u; 27     edge[NE].cap=0; 28     edge[NE].cost=-cost; 29     edge[NE].next=head[v]; 30     head[v]=NE++; 31 } 32  33 bool mark[MAXN]; 34 int dist[MAXN]; 35 int pre[MAXN],cur[MAXN]; 36  37  38 bool spfa(int vs,int vt) 39 { 40     memset(mark,false,sizeof(mark)); 41     fill(dist,dist+vt+1,inf); 42     memset(pre,-1,sizeof(pre)); 43     queue
           
            que; 44 que.push(vs); 45 mark[vs]=true; 46 dist[vs]=0; 47 while(!que.empty()){ 48 int u=que.front(); 49 que.pop(); 50 mark[u]=false; 51 for(int i=head[u];i!=-1;i=edge[i].next){ 52 int v=edge[i].v,cost=edge[i].cost; 53 if(edge[i].cap>0&&dist[u]+cost