題意：給出N個點，M條邊，問從1-N來回走一次最短路徑是多少，且一條邊只能經過一次。
直接一遍費用流即可。不過題目中初值需要注意，貢獻了幾次WA。
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 100005
#define inf 2000000000//一開始inf = 1 << 28 但是WA，所以注意一下，這個初值得大。
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
inline void readint(int &ret)
{
char c;
do
{
c = getchar();
}
while(c < '0' || c > '9');
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
int n , m ;
struct kdq
{
int s ,e ,l , c ,next ;
}ed[1000005] ;
int head[10005] ,num ;
void add(int s ,int e ,int l ,int c)
{
ed[num].s = s ;
ed[num].e = e ;
ed[num].l = l ;
ed[num].c = c ;
ed[num].next = head[s] ;
head[s] = num ++ ;
ed[num].s = e ;
ed[num].e = s ;
ed[num].l = 0 ;
ed[num].c = -c ;
ed[num].next = head[e] ;
head[e] = num ++ ;
}
int S , T ;
void init()
{
mem(head,-1) ;
num = 0 ;
}
int dis[Max] ;
bool vis[Max] ;
int qe[Max * 10] ;
int pre[Max] ,path[Max] ;
int spfa()
{
REP(i,0,T)dis[i] = inf ,vis[i] = 0 ;
dis[S] = 0 ;
vis[S] = 1 ;
int h = 0 , t = 0 ;
qe[h ++ ] = S ;
while( h > t )
{
int tt = qe[t ++ ] ;
vis[tt] = 0 ;
for (int i = head[tt] ;~i ;i = ed[i].next )
{
int ee = ed[i].e ;
int l = ed[i].l ;
int c = ed[i].c ;
if(l > 0 && dis[ee] > dis[tt] + c)
{
pre[ee] = tt ;
path[ee] = i ;
dis[ee] = dis[tt] + c ;
if(!vis[ee])
{
vis[ee] = 1 ;
qe[h ++ ] = ee ;
}
}
}
}
return dis[T] != inf ;
}
int MFMC()
{
int M = 0 ;
while(spfa())
{
int ff = inf ;
for (int i = T ;i != S ;i = pre[i])
ff = min(ff , ed[path[i]].l) ;
for (int i = T ;i != S ;i = pre[i])
ed[path[i]].l -= ff ,ed[path[i] ^ 1].l += ff ;
M += dis[T] * ff ;
}
return M ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("acm.txt", "r", stdin);
#endif
init() ;
readint(n) ;
readint(m) ;
S = 0 ,T = n + 1 ;
REP(i,0,m - 1)
{
int a , b , c ;
readint(a) ;
readint(b) ;
readint(c) ;
add(a,b,1,c) ;
add(b,a,1,c) ;
}
add(S,1,2,0) ;
add(n,T,2,0) ;
cout << MFMC() << endl;
return 0;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 100005
#define inf 2000000000//一開始inf = 1 << 28 但是WA，所以注意一下，這個初值得大。
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
inline void readint(int &ret)
{
char c;
do
{
c = getchar();
}
while(c < '0' || c > '9');
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
int n , m ;
struct kdq
{
int s ,e ,l , c ,next ;
}ed[1000005] ;
int head[10005] ,num ;
void add(int s ,int e ,int l ,int c)
{
ed[num].s = s ;
ed[num].e = e ;
ed[num].l = l ;
ed[num].c = c ;
ed[num].next = head[s] ;
head[s] = num ++ ;
ed[num].s = e ;
ed[num].e = s ;
ed[num].l = 0 ;
ed[num].c = -c ;
ed[num].next = head[e] ;
head[e] = num ++ ;
}
int S , T ;
void init()
{
mem(head,-1) ;
num = 0 ;
}
int dis[Max] ;
bool vis[Max] ;
int qe[Max * 10] ;
int pre[Max] ,path[Max] ;
int spfa()
{
REP(i,0,T)dis[i] = inf ,vis[i] = 0 ;
dis[S] = 0 ;
vis[S] = 1 ;
int h = 0 , t = 0 ;
qe[h ++ ] = S ;
while( h > t )
{
int tt = qe[t ++ ] ;
vis[tt] = 0 ;
for (int i = head[tt] ;~i ;i = ed[i].next )
{
int ee = ed[i].e ;
int l = ed[i].l ;
int c = ed[i].c ;
if(l > 0 && dis[ee] > dis[tt] + c)
{
pre[ee] = tt ;
path[ee] = i ;
dis[ee] = dis[tt] + c ;
if(!vis[ee])
{
vis[ee] = 1 ;
qe[h ++ ] = ee ;
}
}
}
}
return dis[T] != inf ;
}
int MFMC()
{
int M = 0 ;
while(spfa())
{
int ff = inf ;
for (int i = T ;i != S ;i = pre[i])
ff = min(ff , ed[path[i]].l) ;
for (int i = T ;i != S ;i = pre[i])
ed[path[i]].l -= ff ,ed[path[i] ^ 1].l += ff ;
M += dis[T] * ff ;
}
return M ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("acm.txt", "r", stdin);
#endif
init() ;
readint(n) ;
readint(m) ;
S = 0 ,T = n + 1 ;
REP(i,0,m - 1)
{
int a , b , c ;
readint(a) ;
readint(b) ;
readint(c) ;
add(a,b,1,c) ;
add(b,a,1,c) ;
}
add(S,1,2,0) ;
add(n,T,2,0) ;
cout << MFMC() << endl;
return 0;
}
