n个点 m条边
给m条边
求1->n n->1 最小花费,每条边最多走一次
两个最短路显然不行 会影响另外一条
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<math.h> using namespace std; #define inf 100000000
#define MAXN 50000
#define MAXN1 1500 struct node
{
int fr,to,next,fl,w; }x[MAXN];
int cnt,S,T;
int head[MAXN1],dis[MAXN1],pre[MAXN1];
bool vis[MAXN1]; void add(int u,int v,int fl,int w)
{
x[cnt].fr=u;
x[cnt].next=head[u];
x[cnt].to=v;
x[cnt].fl=fl;
x[cnt].w=w;
head[u]=cnt++;
}
queue<int>q1; int spfa() //最短路的话就是可以增广 费用最少
{
memset(vis,,sizeof(vis));
memset(pre,-,sizeof(pre));
int i;
for(i=;i<=T;i++)
dis[i]=inf;
dis[S]=;
vis[S]=;
q1.push(S);
while(!q1.empty())
{
int now=q1.front();
q1.pop();
vis[now]=;
for(i=head[now];i!=-;i=x[i].next)
{
if(dis[now]+x[i].w<dis[x[i].to]&&x[i].fl)
{
dis[x[i].to]=dis[now]+x[i].w;
pre[x[i].to]=i;
if(vis[x[i].to]==)
{
q1.push(x[i].to);
vis[x[i].to]=;
}
}
}
}
int a=pre[T];
while(a!=-) //要结束了也可以更新流量
{
x[a].fl-=;
x[a^].fl+=;
a=pre[x[a].fr];
}
return pre[T]!=-;
} int main()
{
int n,m; while(scanf("%d%d",&n,&m)!=EOF)
{
int i;
cnt=;
memset(head,-,sizeof(head));
S=,T=n+;
for(i=;i<=m;i++)
{
int a,b,w; scanf("%d%d%d",&a,&b,&w);
add(a,b,,w),add(b,a,,-w); //-w 如果有一条更优的路 可以走回来+（-w）;
add(b,a,,w),add(a,b,,-w);
}
add(S,,,),add(,S,,); //其实就是2次 1->n
add(n,T,,),add(T,n,,);
int ans=;
while(spfa())
ans=ans+dis[T];
printf("%d\n",ans);
}
return ;
}