#P3068. "Shortest" pair of paths

"Shortest" pair of paths

描述

某化工公司遇到了一个特殊的最短路径问题。

公司有NN个仓库(顶点)用于存储化学品,以及MM种运输方式(有向边)连接这些仓库。每种运输方式都有一个成本。在常规问题中,公司只需找到从起始仓库(00)到目标仓库(N1N-1)的单条运输路径,这很简单。但当前的问题更加复杂:

公司需要同时运输两种化学品,从仓库00到仓库N1N-1。这两种化学品具有危险性,不能共存于同一运输方式或同一仓库(除了起始和终点仓库00N1N-1)。具体约束如下:

  1. 运输路径分离:两条路径不能使用相同的运输方式(边)。
  2. 仓库分离:两条路径在运输过程中不能经过相同的仓库(顶点),除了起点00和终点N1N-1
  3. 目标:在满足上述约束的条件下,找到总运输成本最低的两条路径。若无法实现,则判定为不可行。

输入

输入包含多个测试用例。每个用例的第一行给出NN(仓库数量,N<64N < 64)和MM(运输方式数量,M<10000M < 10000)。接下来的MM行,每行包含三个整数iijjvv,表示一条从仓库ii到仓库jj、成本为vv有向运输方式(可能存在重边)。输入以0 00\ 0结束。

输出

对每个测试用例,输出一行:

  • 若存在可行解,输出 Instance #<编号>: <最小总成本>
  • 若不可行,输出 Instance #<编号>: Not possible

输入样例 1

2 1
0 1 20
2 3
0 1 20
0 1 20
1 0 10
4 6
0 1 22
1 3 11
0 2 14
2 3 26
0 3 43
0 3 58
0 0

输出样例 1

Instance #1: Not possible
Instance #2: 40
Instance #3: 73

来源

2006年东南欧地区赛