#P3511. [POI 2010] MOS-Bridges
[POI 2010] MOS-Bridges
题目描述
San Bytecisco 是一个风景优美的沿海小镇。
它由一些小而人口稠密的岛屿组成,编号从 到 。
某些岛屿之间通过桥梁连接,用于双向的道路交通。
每对岛屿之间最多有一座桥。
这些岛屿之间连接的桥梁使得每个岛屿都可以到达其他岛屿。
Byteasar 和 Bytie 正计划在 San Bytecisco 骑自行车旅行。
他们将从 号岛出发。
他们打算访问每个岛屿,同时每座桥只经过一次,并在旅行结束时回到出发地,即 号岛。
作为经验丰富的骑手,他们预计会遇到一些严重的麻烦……风!
毕竟,沿海地区风很大,尤其是在岛屿之间的桥上。显然,根据风速和方向,风使得跨越桥梁面临不同程度上的困难。
为了简单起见,我们假设每座桥的任意一个跨越方向遭到的逆风的速度是恒定的。
Byteasar 和 Bytie 决定将遭到的逆风的最大速度作为路线疲劳程度的衡量标准。帮助 Byteasar 和 Bytie 找到他们想要的路线,使得这条路线的疲劳程度最小。
输入格式
标准输入的第一行有两个用空格分隔的整数: 和 (,),分别表示 San Bytecisco 的岛屿数量和桥梁数量。岛屿编号从 到 ,桥梁编号从 到 。接下来的 行给出了桥梁。第 行包含四个用空格分隔的整数 (),表示第 号桥连接了第 号和第 号岛屿。当从 到 移动时遭到的逆风的速度为 ,而从 到 移动时遭到的逆风的速度为 。
输出格式
如果没有满足这两位勇敢骑手要求的路线,标准输出的第一行应为单词 NIE(波兰语中的“不”)。
否则,输出应有两行,指定 San Bytecisco 上最不疲劳的路线。
第一行应包含该路线遭到的逆风的最大速度,即我们希望最小化的数字。
第二行应包含 个整数,用空格分隔,表示在最不疲劳的路线中依次经过的桥梁编号。
如果有多条最不疲劳的路线,你可以输出任意一条。
4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
4
4 3 2 1
提示
,,,,。
题面翻译由 ChatGPT-4o 提供。