#P1359. P1359 租用游艇

P1359 租用游艇

P1359 租用游艇

普及- | 来源:洛谷 | 原题链接

题意

长江上依次设 nn 个游艇出租站 1∼n1 \sim n。游客可在任一站租船、在下游任一站还船,从站 ii 租到站 jj(i<ji<j)的租金为 ri,jr_{i,j}。求从站 11 到站 nn 的最少总租金。输入是半矩阵:第 ii 行给出 ri,i+1, ri,i+2,…,ri,nr_{i,i+1},\ r_{i,i+2},\dots,r_{i,n}。

输入格式

第一行中有一个正整数 nn,表示有 nn 个游艇出租站。接下来的 n−1n-1 行是一个半矩阵 ri,jr_{i,j}(1≤i<j≤n1\le i<j\le n)。

输出格式

输出计算出的从游艇出租站 11 到游艇出租站 nn 所需的最少租金。

输入输出样例

样例 1 输入

3
5 15
7

样例 1 输出

12

数据范围

1≤n≤2001\le n\le 200;租金为正整数,保证计算过程中任何时刻数值不超过 10610^6。

提示

考点:Dijkstra 最基本形态(O(n2)O(n^2) 朴素版即可)。易错点:半矩阵只给 i<ji<j 的部分,读入时第 ii 行恰好 n−in-i 个数;边方向只能是「下游」i→ji\to j(i<ji<j)。

蜀ICP备2025119001号-1