题意：给定一个有向带权图，求两条不相交（无公共点）的路径且路径权值之和最小，路径由1到v
题解：这题的关键就在于每个点只能走一遍，于是我们想到以边换点的思想，用边来代替点，怎么代替呢？
把i拆成i和i'，这样经过i就转化为经过i到i'的路径了，从而用最小费用流即可
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define MAXN 5005
#define ll long long
#define INF 0x7f7f7f7f
using namespace std;
struct Edge{
int from,to,cap,flow,cost;
Edge(int u=,int v=,int c=,int f=,int w=){
from=u,to=v,cap=c,flow=f,cost=w;
}
};
struct MCMF{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[MAXN];
int d[MAXN];
int p[MAXN];
int b[MAXN];
int a[MAXN];
void init(int n,int s,int t){
this->n=n;
this->s=s,this->t=t;
edges.clear();
for(int i=;i<=n;i++){
G[i].clear();
}
}
void AddEdge(int x,int y,int cap,int cost){
edges.push_back(Edge(x,y,cap,,cost));
edges.push_back(Edge(y,x,,,-cost));
m=edges.size();
G[x].push_back(m-);
G[y].push_back(m-);
}
int SPFA(int &flow,ll &cost){
memset(d,0x7f,sizeof(d));
memset(b,,sizeof(b));
queue<int> q;
p[s]=;
a[s]=INF;
d[s]=;
q.push(s);
b[s]=;
while(!q.empty()){
int x=q.front();q.pop();
b[x]=;
for(int i=;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(e.cap>e.flow&&d[e.to]>d[x]+e.cost){
p[e.to]=G[x][i];
a[e.to]=min(a[x],e.cap-e.flow);
d[e.to]=d[x]+e.cost;
if(!b[e.to]){
b[e.to]=;
q.push(e.to);
}
}
}
}
if(d[t]==INF){
return ;
}
flow+=a[t];
cost+=1LL*d[t]*a[t];
for(int i=t;i!=s;i=edges[p[i]].from){
edges[p[i]].flow+=a[t];
edges[p[i]^].flow-=a[t];
}
return ;
}
ll MincostMaxflow(){
int flow=;ll cost=;
while(SPFA(flow,cost));
return cost;
}
}D;
int n,m;
int main()
{
while(~scanf("%d%d",&n,&m)){
D.init(n<<,,n);
D.AddEdge(,,,);
for(int i=;i<=n;i++){
D.AddEdge(i,i+n,,);
}
for(int i=;i<=m;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
if(x==||x==n)
D.AddEdge(x,y,,1LL*w);
else
D.AddEdge(x+n,y,,1LL*w);
}
printf("%lld\n",D.MincostMaxflow());
}
return ;
}