#P1359. P1359 租用游艇
P1359 租用游艇
P1359 租用游艇
普及- | 来源:洛谷 | 原题链接
题意
长江上依次设 个游艇出租站 。游客可在任一站租船、在下游任一站还船,从站 租到站 ()的租金为 。求从站 到站 的最少总租金。输入是半矩阵:第 行给出 。
输入格式
第一行中有一个正整数 ,表示有 个游艇出租站。接下来的 行是一个半矩阵 ()。
输出格式
输出计算出的从游艇出租站 到游艇出租站 所需的最少租金。
输入输出样例
样例 1 输入
3
5 15
7
样例 1 输出
12
数据范围
;租金为正整数,保证计算过程中任何时刻数值不超过 。
提示
考点:Dijkstra 最基本形态( 朴素版即可)。易错点:半矩阵只给 的部分,读入时第 行恰好 个数;边方向只能是「下游」()。