题目描述

长江游艇俱乐部在长江上设置了 nn 个游艇出租站 1,2,\cdots,n1,2,⋯,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 ii 到游艇出租站 jj 之间的租金为 r(i,j)r(i,j)（1\le i\lt j\le n1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 11 到游艇出租站 nn 所需的最少租金。

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

3
5 15
7

输出 #1复制

12

#include<bits/stdc++.h>
using namespace std;
int vis[10000];
int low[10000];
int Map[10000][10000];
int const inf=1e9;
int n,k;//k指边的数量；
int Dijkstra(int bg,int nd)
{
    for(int i=1;i<=n;i++)
    {
        low[i]=inf;
        vis[i]=0;
    }//初始化数据
    vis[bg]=1;
    for(int i=1;i<=n;i++)
    {
        if(low[i]>Map[bg][i])//标记每两点间初始的长度
            low[i]=Map[bg][i];
    }
    for(int i=2;i<=n;i++)//找到起始点到达所有中转点(未被标记)中距离最小的中转点
    {
        int Min=inf,s=-1;
        for(int j=2;j<=n;j++)
        {
            if(vis[j]==0&&low[j]<Min)
            {
                Min=low[j];
                s=j;
            }
        }
        vis[s]=1;//将该中转点标记
        //cout<<s<<" "<<Min<<endl;
        for(int j=s;j<=n;j++)
        {
            if(low[j]>Min+Map[s][j])//经过中转到达该点的距离和开始到达该点的距离比较
                low[j]=Min+Map[s][j];
                //cout<<j<<" "<<low[j]<<" "<<Map[s][j]<<" "<<Min<<endl;
        }
        //cout<<endl;
    }
    return low[nd];
}
int main()
{
    cin>>n;
    int a,b,c;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
    {
        cin>>c;
        Map[i][j]=c;//单向关系，表示i->j的长度为c
        //Map[j][i]=c;
    }
    cout<<Dijkstra(1,n);
}