租用游艇
题目描述
长江游艇俱乐部在长江上设置了 \(n\) 个游艇出租站 \(1,2,\cdots,n\)。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 \(i\) 到游艇出租站 \(j\) 之间的租金为 \(r(i,j)\)（\(1\le i\lt j\le n\)）。试设计一个算法，计算出从游艇出租站 \(1\) 到游艇出租站 \(n\) 所需的最少租金。
输入格式
第一行中有一个正整数 \(n\)，表示有 \(n\) 个游艇出租站。接下来的 \(n-1\) 行是一个半矩阵 \(r(i,j)\)（\(1\le i<j\le n\)）。
输出格式
输出计算出的从游艇出租站 \(1\) 到游艇出租站 \(n\) 所需的最少租金。
样例 #1
样例输入 #1
3
5 15
7
样例输出 #1
12
提示
\(n\le 200\)，保证计算过程中任何时刻数值都不超过 \(10^6\)。
因为题目数据很小，所以直接Floyd即可，代码很简短，核心就有点类似与dp的状态转移
#include<bits/stdc++.h>
using namespace std;
int a[1000][1000];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=0x3f;
}
}
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
cin>>a[i][j];
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]>a[i][k]+a[k][j]){
a[i][j]=a[i][k]+a[k][j];
}
}
}
}
cout<<a[1][n];
return 0;
}