POJ2135.md

要求两次最短路且不重复，考虑费用流，源点向1号点建边，费用为0，容量为2；n点向汇点建边，费用为0，容量为2；其余边为双向边，容量为1，费用为路长 建图跑费用流即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 1e3+7;
const int INF = 0x3f3f3f3f;
#define S 0
#define T MAXN - 1
int n,m,dist[MAXN],flow[MAXN],pre[MAXN],vis[MAXN],pid[MAXN];
struct EDGE{
    int to, cap, fee, rev;
    EDGE(){}
    EDGE(int _to, int _cap, int _fee, int _rev){ to = _to; cap = _cap; fee = _fee; rev = _rev; }
};
vector<EDGE> G[MAXN];
void ADDEDGE(int u, int v, int cap, int fee){
    G[u].push_back(EDGE(v,cap,fee,(int)G[v].size()));
    G[v].push_back(EDGE(u,0,-fee,(int)G[u].size()-1));
}
bool spfa(){
    memset(dist,INF,sizeof(dist));
    pre[T] = -1;
    flow[S] = INF;
    dist[S] = 0;
    queue<int> que;
    que.push(S);
    memset(vis,0,sizeof(vis));
    while(!que.empty()){
        int u = que.front();
        que.pop();
        vis[u] = false;
        for(int i = 0; i < (int)G[u].size(); i++){
            EDGE &e = G[u][i];
            if(!e.cap) continue;
            if(dist[e.to]>dist[u]+e.fee){
                dist[e.to] = dist[u] + e.fee;
                pre[e.to] = u;
                pid[e.to] = i;
                flow[e.to] = min(flow[u],e.cap);
                if(!vis[e.to]){
                    vis[e.to] = true;
                    que.push(e.to);
                }
            }
        }
    }
    return pre[T]!=-1;
}
int mcmf(){
    int cost = 0;
    while(spfa()){
        cost += flow[T] * dist[T];
        int rt = T;
        while(rt){
            G[pre[rt]][pid[rt]].cap -= flow[T];
            G[rt][G[pre[rt]][pid[rt]].rev].cap += flow[T];
            rt = pre[rt];
        }
    }
    return cost;
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i = 0; i <= n; i++) G[i].clear();
        G[T].clear();
        for(int i = 1; i <= m; i++){
            int u, v, c;
            scanf("%d %d %d",&u, &v, &c);
            ADDEDGE(u,v,1,c);
            ADDEDGE(v,u,1,c);
        }
        ADDEDGE(S,1,2,0);
        ADDEDGE(n,T,2,0);
        printf("%d\n",mcmf());
    }
    return 0;
}