poj 2135 Farm Tour //最小費用流模闆（dijstra實作）

最小費用流模闆（dijstra實作）

Farm Tour

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 21105	Accepted: 8115

Description

When FJ's friends visit him on the farm, he likes to show them around. His farm comprises N (1 <= N <= 1000) fields numbered 1..N, the first of which contains his house and the Nth of which contains the big barn. A total M (1 <= M <= 10000) paths that connect the fields in various ways. Each path connects two different fields and has a nonzero length smaller than 35,000. 

To show off his farm in the best way, he walks a tour that starts at his house, potentially travels through some fields, and ends at the barn. Later, he returns (potentially through some fields) back to his house again. 

He wants his tour to be as short as possible, however he doesn't want to walk on any given path more than once. Calculate the shortest tour possible. FJ is sure that some tour exists for any given farm.

Input

* Line 1: Two space-separated integers: N and M. 

* Lines 2..M+1: Three space-separated integers that define a path: The starting field, the end field, and the path's length. 

Output

A single line containing the length of the shortest tour. 

Sample Input

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2
           

Sample Output

6
           

題意：求不重複的兩條最短路(無向邊)。

可以轉換為求1-n的兩條沒有公共邊的路的最小花費，這樣建立流量為2的最小費用流即可。（日常signed）

複雜度（FElogV)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<climits>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
const int max_n=1005;
struct no{int to,cap,cost,rev;};
struct qno{int v,d;}; //隊列節點
bool operator<(const qno &x,const qno &y) {return x.d>y.d;} //隊列cmp重寫
int n,m;  //定點數 和邊數
vector<no>g[max_n];
int dis[max_n],h[max_n]; //最短距離，頂點的勢
int prevv[max_n],preve[max_n]; //在vector下記錄路徑

void addedge(int from,int to,int cap,int cost){
    g[from].push_back((no){to,cap,cost,g[to].size()});
    g[to].push_back((no){from,0,-cost,g[from].size()-1});
}
int min_cost_flow(int s,int t,int f){//注意n變化了！！！！！！！！！！！！！！！！！
    int res=0; //answer
    for(int i=0;i<=n;i++) h[i]=0; //初始化h
    while(f>0){
        priority_queue<qno>q;
        for(int i=0;i<=n;i++) dis[i]=INT_MAX/2;
        dis[s]=0;
        q.push((qno){s,0});
        while(!q.empty()){
            qno now=q.top();q.pop();
            int v=now.v;
            if(dis[v]<now.d) continue;
            for(int i=0;i<g[v].size();i++){
                no &e=g[v][i];
                if(e.cap>0&&dis[e.to]>dis[v]+e.cost+h[v]-h[e.to]){ //加入啦勢
                    dis[e.to]=dis[v]+e.cost+h[v]-h[e.to];
                    prevv[e.to]=v;
                    preve[e.to]=i;
                    q.push((qno){e.to,dis[e.to]});
                }
            }
        }
        if(dis[t]==INT_MAX/2) return -1;
        for(int v=0;v<=n;v++) h[v]+=dis[v];
        int d=f; //找增廣路
        for(int v=t;v!=s;v=prevv[v]) d=min(d,g[prevv[v]][preve[v]].cap);
        f-=d;res+=d*h[t];
        for(int v=t;v!=s;v=prevv[v]){
            no &e=g[prevv[v]][preve[v]];
            e.cap-=d;
            g[v][e.rev].cap+=d;
        }
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        addedge(u,v,1,w);
        addedge(v,u,1,w);
    }
    cout<<min_cost_flow(1,n,2);
    return 0;
}