2018年4月月赛 Day1 游艇题解

题目描述

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

对于给定的游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1<=i<j<=n。

保证计算过程中任何时刻数值都不超过10^6

输入输出格式

输入格式

第1 行中有1 个正整数n，表示有n个游艇出租站。接下来的n-1 行,第i行第j个元素表示从i号游艇出租站到j号游艇出租站(1<=i<j<=n)的租金价格r。

输出格式

共n-1行，第i行输出i-1个数，每行第j个数表示从i号游艇出租站出发到达第j号游艇出租站的最少租金。

输入输出样例

输入样例#1：

1
2
3

3
5 15
7

输出样例#1：

1
2

5 12
7

说明

1<=n<=200

Floyd板子题……

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,d[210][210];
void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=k;i++)
            for(int j=k+1;j<=n;j++)
                if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            scanf("%d",&d[i][j]);
    floyd();
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++) cout<<d[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}