#P3068. "Shortest" pair of paths
"Shortest" pair of paths
描述
某化工公司遇到了一个特殊的最短路径问题。
公司有个仓库(顶点)用于存储化学品,以及种运输方式(有向边)连接这些仓库。每种运输方式都有一个成本。在常规问题中,公司只需找到从起始仓库()到目标仓库()的单条运输路径,这很简单。但当前的问题更加复杂:
公司需要同时运输两种化学品,从仓库到仓库。这两种化学品具有危险性,不能共存于同一运输方式或同一仓库(除了起始和终点仓库和)。具体约束如下:
- 运输路径分离:两条路径不能使用相同的运输方式(边)。
- 仓库分离:两条路径在运输过程中不能经过相同的仓库(顶点),除了起点和终点。
- 目标:在满足上述约束的条件下,找到总运输成本最低的两条路径。若无法实现,则判定为不可行。
输入
输入包含多个测试用例。每个用例的第一行给出(仓库数量,)和(运输方式数量,)。接下来的行,每行包含三个整数、、,表示一条从仓库到仓库、成本为的有向运输方式(可能存在重边)。输入以结束。
输出
对每个测试用例,输出一行:
- 若存在可行解,输出
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年东南欧地区赛