从起点到终点找两条没有公共端点的路径，使得权值和最小，这是老套路了
保证每个点只经过一次，可以拆点
然后跑流量为2的费用流
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdlib> #include <utility> #include <map> #include <stack> #include <set> #include <vector> #include <queue> #include <deque> #include <sstream> #define x first #define y second #define mp make_pair #define pb push_back #define LL long long #define Pair pair<int,int> #define LOWBIT(x) x & (-x) using namespace std; const int MOD=1e9+7; const int INF=0x7ffffff; const int magic=348; int n,e; int start,ed; int prevv[100048],preve[100048],h[100048]; int t,tot,head[100048],to[200048],f[200048],nxt[200048],w[200048]; inline void addedge(int s,int t,int cap,int cost) { to[++tot]=t;nxt[tot]=head[s];head[s]=tot;f[tot]=cap;w[tot]=cost; to[++tot]=s;nxt[tot]=head[t];head[t]=tot;f[tot]=0;w[tot]=-cost; } int dist[100048];priority_queue<Pair> q; void dijkstra() { int i,x,y,dd; for (i=1;i<=t;i++) dist[i]=INF; dist[start]=0;q.push(mp(0,start)); while (!q.empty()) { x=q.top().y;dd=-q.top().x;q.pop(); if (dist[x]<dd) continue; for (i=head[x];i;i=nxt[i]) { y=to[i]; if (f[i] && dist[y]>dist[x]+w[i]+h[x]-h[y]) { dist[y]=dist[x]+w[i]+h[x]-h[y]; prevv[y]=x;preve[y]=i; q.push(mp(-dist[y],y)); } } } } int min_cost_flow() { int i,minf,u,res=0; for (i=1;i<=t;i++) h[i]+=dist[i]; minf=INF; for (u=ed;u!=start;u=prevv[u]) minf=min(minf,f[preve[u]]); res=minf*h[ed]; for (u=ed;u!=start;u=prevv[u]) { f[preve[u]]-=minf; f[preve[u]^1]+=minf; } return res; } int main () { int i,j,x,y,c; while (scanf("%d%d",&n,&e)!=EOF) { t=n*2;tot=1; for (i=1;i<=t;i++) head[i]=0; for (i=1;i<=t;i++) h[i]=0; for (i=1;i<=n;i++) addedge(i,n+i,1,0); for (i=1;i<=e;i++) { scanf("%d%d%d",&x,&y,&c); addedge(n+x,y,1,c); } int ans=0;start=n+1;ed=n; for (i=1;i<=2;i++) { dijkstra(); ans+=min_cost_flow(); } printf("%d\n",ans); } return 0; }