【题意】：Farmer John（FJ）想带他的朋友逛逛他的农场，给出n表示他农场的个数（1代表他的家，n代表谷仓），m表示建筑之间连接的路的个数。他想从他的家出发，然后通过一些农场，最后到达他的谷仓。然后，又从谷仓出发，通过一些农场，最后回到他的家。他要求旅游的路径最短，并且不走重复的路。FJ确信总是存在可行解，问最短的路径是多少？
【题解】：简化问题，其实就是在不走重复的路的条件下，求两次从1走到n的最短路。
然后我们很容易就想到费用流，要找最短路径，那显然就是最小费用流。
把路长看成费用，然后如果u和v之间有路（这里是双向路），那么连边u->v,v->u，费用都是路长，容量都为1，表示只能走一次。
加入一个源点s，连边s->1，费用为0，容量为2，表示增广两次，即求两次最短路径。
汇点t直接就是n了。然后求s到t的最小费用流，最后的费用就是答案了。
这题可以有点小优化，只需要记录费用就可以了，因为最后的流肯定是2，而且每条边的容量都是1，那么每一次增广出来的流肯定为1，就不用每次比较取增广路上最小的容量了。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "string"
4 #include "queue"
5 using namespace std;
6 #define bigint __int64
7 #define maxn 1005
8 #define maxm 40005
9 const bigint INF = 99999999;
10 int n, m;
11 int s, t;
12 int eh[maxn], tot, p[maxn];
13 bigint dist[maxn], anscost;
14 bool visit[maxn];
15
16 struct Edge {
17 int u, v;
18 bigint cost, cap, flow;
19 int next;
20 }et[maxm];
21
22 void add(int u, int v,bigint cost, bigint cap,bigint flow) {
23 Edge e = {u, v, cost, cap, flow, eh[u]};
24 et[tot] = e;
25 eh[u] = tot++;
26 }
27
28 void addedge(int u, int v, bigint cost, bigint cap) {
29 add(u, v, cost, cap, 0), add(v, u, -cost, 0, 0);
30 }
31
32 void init() {
33 tot = 0;
34 memset(eh, -1, sizeof(eh));
35 }
36
37 bool spfa() {
38 queue<int> que;
39 memset(visit, false, sizeof(visit));
40 memset(p, -1, sizeof(p));
41 fill(&dist[0], &dist[maxn], INF);
42 visit[s] = true, dist[s] = 0;
43 que.push(s);
44 while(!que.empty()) {
45 int u = que.front();
46 que.pop();
47 visit[u] = false;
48 for(int i = eh[u]; i != -1; i = et[i].next) {
49 int v = et[i].v;
50 bigint cost = et[i].cost, cap = et[i].cap, flow = et[i].flow;
51 if(flow < cap && dist[u] + cost < dist[v]) {
52 dist[v] = dist[u] + cost;
53 p[v] = i;
54 if(!visit[v]) {
55 visit[v] = true;
56 que.push(v);
57 }
58 }
59 }
60 }
61 return dist[t] != INF;
62 }
63
64 void costflow() {
65 anscost = 0;
66 while(spfa()) {
67 int x = p[t];
68 anscost += dist[t];
69 while(x != -1) {
70 et[x].flow++;
71 et[x^1].flow--;
72 // et[x^1].cost = -et[x].cost;
73 x = p[et[x].u];
74 }
75 }
76 }
77
78 int main() {
79 init();
80 int u, v;
81 bigint cost;
82 scanf("%d%d", &n, &m);
83 for(int i = 0; i < m; i++) {
84 scanf("%d%d%I64d", &u, &v, &cost);
85 addedge(u, v, cost, 1);
86 addedge(v, u, cost, 1);
87 }
88 s = 0, t = n;
89 addedge(s, 1, 0, 2);
90 costflow();
91 printf("%I64d\n", anscost);
92 return 0;
93 }