题目大意：
从起点1到终点N的一个圈，最小路径花费。完毕。
构图跑两次spfa，完毕。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define NN 1111
#define MN 11111
using namespace std;struct Edge{ int u,v,c,f,cost,next; }E[MN<<2];
int head[NN],dis[NN],cur[NN],pre[NN];
int EN,s,t;
bool vis[NN];void addEdge( int u,int v,int c,int cost )
{E[EN].v=v; E[EN].c=c; E[EN].f=0; E[EN].cost=cost;E[EN].next=head[u]; head[u]=EN++;E[EN].v=u; E[EN].c=0; E[EN].f=0; E[EN].cost=-cost;E[EN].next=head[v]; head[v]=EN++;
}void spfa()
{memset( vis,0,sizeof(vis) );memset( dis,0x3f,sizeof(dis) );queue<int>Q;dis[s]=0;pre[s]=s;Q.push(s);while( !Q.empty() ){int cc=Q.front();Q.pop();vis[cc]=false;for( int i=head[cc];i!=-1;i=E[i].next ){if( dis[E[i].v]>dis[cc]+E[i].cost && E[i].f<E[i].c ){dis[E[i].v]=dis[cc]+E[i].cost;pre[E[i].v]=cc;cur[E[i].v]=i;if( !vis[E[i].v] ){Q.push(E[i].v);vis[E[i].v]=true;}}}}
}int main()
{int N,M;while( scanf("%d %d",&N,&M)!=EOF ){int u,v,cost;memset( head,-1,sizeof(head) );s=0;t=N+1;for( int i=0;i<M;i++ ){scanf( "%d %d %d",&u,&v,&cost );addEdge( u,v,1,cost );addEdge( v,u,1,cost );}addEdge( s,1,2,0 ); addEdge( N,t,2,0 );int ans=0;while( true ){spfa();int aug=0x3f3f3f3f;if( dis[t]==0x3f3f3f3f )break;for( int i=t;i!=s;i=pre[i] )aug=min( aug,E[cur[i]].c-E[cur[i]].f );for( int i=t;i!=s;i=pre[i] ){E[cur[i]].f+=aug;E[cur[i]^1].f-=aug;}ans+=aug*dis[t];}printf( "%d\n",ans );}return 0;
}