租用游艇

题目描述

长江游艇俱乐部在长江上设置了 \(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;
}