Double Shortest Paths
Alice and Bob are walking in an ancient maze with a lot of caves and one-way passages connecting
them. They want to go from cave 1 to cave n. All the passages are difficult to pass. Passages are too
small for two people to walk through simultaneously, and crossing a passage can make it even more
difficult to pass for the next person. We define di as the difficulty of crossing passage i for the first time,
and ai as the additional difficulty for the second time (e.g. the second person’s difficulty is di + ai).
Your task is to find two (possibly identical) routes for Alice and Bob, so that their total difficulty
is minimized.
For example, in figure 1, the best solution is 1 → 2 → 4 for both Alice and Bob, but in figure 2, it’s
better to use 1 → 2 → 4 for Alice and 1 → 3 → 4 for Bob. It’s always possible to reach cave n
from cave 1.
Input
There will be at most 200 test cases. Each case begins with two integers n, m (1 ≤ n ≤ 500, 1 ≤
m ≤ 2000), the number of caves and passages. Each of the following m lines contains four integers u,
v, di and ai (1 ≤ u, v ≤ n, 1 ≤ di ≤ 1000, 0 ≤ ai ≤ 1000). Note that there can be multiple passages
connecting the same pair of caves, and even passages connecting a cave and itself.
Output
For each test case, print the case number and the minimal total difficulty.
Sample Input
4 4
1 2 5 1
2 4 6 0
1 3 4 0
3 4 9 1
4 4
1 2 5 10
2 4 6 10
1 3 4 10
3 4 9 10
Sample Output
Case 1: 23
Case 2: 24
这是偶做的一条MCMF。
一开始想dij一次最短路。然后用dfs再记录下来。然后换路。在dij一次。
然后发现这样有可能是错的 。。 因为用一种情况是 2 次都经过了 最短路的一部分 。
。 是有可能小于走完整条最短路 ，然后再多走一次最短路的。。。
例如 。。
后来州神给出来一个样例。
然而， u ,v 构一条费用为 w 流量为1 。一条为w + a ，流量也为1的边
然后源和汇到1 ， n的费用为0，流量为2 ， 求出来就是才是真正的答案 ...