【題意】：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 }