题目地址：http://poj.org/problem?id=2135
由于去和回来可以看成：2条从1到n的不同的路。所以转化成求从1到n的两条不同的路。
建立一个源点，连接1号景点，无费用，容量为2（表示可以有两条路）
同理，建立一个汇点，连接n号景点，无费用，容量为2.
这样，如果求的的最大流是2，就表示了有两条从1到n的不同的路。（因为中间的点边容量只是1，只能用一次）
这样求的最小费用最大流的最小费用就是最短路径长度。
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000+5;
const int INF=1000000000;
struct Edge{int from,to,flow,weight;Edge(int f,int t,int fl,int w):from(f),to(t),flow(fl),weight(w){}
};
vector<Edge> edges;
vector<vector<int> > G(maxn);
bool inq[maxn]; //判断是否在队列里
int dist[maxn];
int prev[maxn]; //记录路径
void AddEdge(int u,int v,int fl,int w)
{edges.push_back(Edge(u,v,fl,w));G[u].push_back(edges.size()-1);
}
bool Spfa(int s,int t)
{memset(inq,false,sizeof(inq));fill(dist,dist+t+2,INF);memset(prev,-1,sizeof(prev));queue<int> Q;dist[s]=0;inq[s]=true; Q.push(s);while(!Q.empty()){int u=Q.front(); Q.pop();inq[u]=false;for(int i=0;i<G[u].size();i++){int v=edges[G[u][i]].to, w=edges[G[u][i]].weight, flow=edges[G[u][i]].flow;if(flow>0&&dist[v]>dist[u]+w) //要在flow>0情况下 {dist[v]=dist[u]+w;prev[v]=G[u][i];if(!inq[v]) Q.push(v),inq[v]=true;}}}return dist[t]!=INF;
}
int solve(int n)
{int s=0,t=n+1;int Mindist=0;AddEdge(s,1,2,0);AddEdge(1,s,0,0);AddEdge(n,t,2,0);AddEdge(t,n,0,0);while(Spfa(s,t)) //从s到t找到一条最小费用通路 {Mindist+=dist[t];int MinFlow=INF; int v=t;while(v!=s){ //计算途中最小流 Edge e=edges[prev[v]];int u=e.from;MinFlow=min(MinFlow,e.flow);v=u;}v=t;while(v!=s){int u=edges[prev[v]].from;edges[prev[v]].flow-=MinFlow; edges[prev[v]^1].flow+=MinFlow; edges[prev[v]^1].weight=-edges[prev[v]].weight; //反向边的cost设为负的 v=u;}}return Mindist;
}
int main()
{int m,n,u,v,w;while(scanf("%d%d",&n,&m)!=EOF){ edges.clear();for(int i=0;i<=n+1;i++) G[i].clear();for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);AddEdge(u,v,1,w); //i 是u->v边 AddEdge(v,u,1,w); //i^1是v->u边 }cout<<solve(n)<<endl;} return 0;
}