【题目链接】 

 

【题目大意】

　　有一张无向图，求从1到n然后又回来的最短路

　　同一条路只能走一次

 

【题解】

　　题目等价于求从1到n的两条路，使得两条路的总长最短

　　那么就等价于求总流量为2的费用流

 

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int INF=0x3f3f3f3f;typedef pair
           
             P;struct edge{int to,cap,cost,rev;};const int MAX_V=1000;int V,h[MAX_V],dist[MAX_V],prevv[MAX_V],preve[MAX_V];vector
            
              G[MAX_V]; void add_edge(int from,int to,int cap,int cost){ G[from].push_back((edge){to,cap,cost,G[to].size()}); G[to].push_back((edge){from,0,-cost,G[from].size()-1});}int min_cost_flow(int s,int t,int f){ int res=0; fill(h,h+V,0); while(f>0){ priority_queue
             
              
,greater
              
 > que; fill(dist,dist+V,INF); dist[s]=0; que.push(P(0,s)); while(!que.empty()){ P p=que.top(); que.pop(); int v=p.second; if(dist[v]
               
                0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){ dist[e.to]=dist[v]+e.cost+h[v]-h[e.to]; prevv[e.to]=v; preve[e.to]=i; que.push(P(dist[e.to],e.to)); } } } if(dist[t]==INF)return -1; for(int v=0;v