acm算法设计：【FLOYD算法】Renting Boats

描述：

长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1< =i< j < =n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需的最少租金。

输入：

第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的n-1 行是r(i,j),1< =i< j < =n。

输出：

从游艇出租站1 到游艇出租站n所需的最少租金

例输入：

3

5 15

7

例输出：

12

-acm algorithm design:【FLOYD algorithm】Renting Boats

Descr iption: Yangtze River Yacht Club has set up in the Yangtze River on a yacht rental n points 1,2, ..., n. Visitors can stand in these yacht rental yacht rental, and any one of the lower reaches of the return of yacht rental yacht station. Yacht rental yacht rental station i to station j rent between r (i, j), 1 < = i < j < = n. Try to design an algorithm to calculate from the yacht rental yacht rental station 1 to station n at least required to rent. Input: line 1 have a positive integer n (n < = 200), said there are n-yacht rental station. The next n-1 line is r (i, j), 1 < = i < j < = n.

Output: from the yacht rental yacht rental station 1 to station n at least required for the importation of rent cases:

3

5,15

7

cases output: 12