Optimal Bus Route Design
题意翻译
最优巴士路线设计
问题描述:
有个大城市想要改进它的公交系统, 其中一个方法就是增加通过景点的观光路线, 你的任务就是为该城的观光公交作一个公交路线计划.
你将会被给出一组景点, 对于每个被给出的景点, 只能有一条公交路线经过, 而且公交路线只能经过这个景点一次. 公交路线的数量可以是无限的, 但每条路线必须至少有两个景点.
连接两个景点的道路是单向的, 对于道路(i,j), 它的长度为d(i,j). 注意即使(i,j)与(j,i)都存在, d(i,j)与d(j,i)也不一定相同. 每条公交路线必须是个有向环.
你需要求出最小的公交路线总长, 即所有公交路线所通过道路的d的总和.
输入格式:
多个子任务. 每个子任务的第一行是一个正整数n, 表示景点个数, 景点用1~n的数表示
接下来n行, 第i+1行描述了以i为起点的单向道路的情况, 其中第(2k-1)个数表示了其中一条道路的终点j, 第2k个数表示d(i,j), 每行以一个单独的'0'结尾.
输入文件以只有一个单独的'0'的一行结尾.
输出格式:
每个子任务占一行, 如果存在符合要求的公交路线, 输出最小的公交路线总长, 否则输出一个字母'N'.
感谢@ajil 提供的翻译
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4095
[PDF](https://uva.onlinejudge.org/external/13/p1349.pdf)