题目描述
长江游艇俱乐部在长江上设置了 \(n\) 个游艇出租站 \(1,2,\cdots,n\)。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 \(i\) 到游艇出租站 \(j\) 之间的租金为 \(r(i,j)\)（\(1 \le i < j \le n\)）。试设计一个算法，计算出从游艇出租站 \(1\) 到游艇出租站 \(n\) 所需的最少租金 。
输入格式
第一行中包含一个正整数 \(n\)，表示有 \(n\) 个游艇出租站。
接下来的 \(n-1\) 行是一个半矩阵 \(r(i,j)\)（\(1 \le i < j \le n\)）。
- 第 \(1\) 行包含 \(n-1\) 个数，分别表示 \(r(1,2), r(1,3), \dots, r(1,n)\)。
- 第 \(2\) 行包含 \(n-2\) 个数，分别表示 \(r(2,3), r(2,4), \dots, r(2,n)\)。
- 以此类推，最后一行（第 \(n-1\) 行）包含 \(1\) 个数，表示 \(r(n-1, n)\) 。
输出格式
输出一个整数，即从游艇出租站 \(1\) 到游艇出租站 \(n\) 所需的最少租金 。
样例数据
输入 #1
3
5 15
7
输出 #1
12
样例解释： 有 3 个游艇出租站。根据输入可知：从站 1 到站 2 的租金为 5，从站 1 到站 3 的租金为 15，从站 2 到站 3 的租金为 7。最省钱的路线是先从 1 到 2（花费 5），再从 2 到 3（花费 7），总租金为 \(5+7=12\) 。
💡 数据范围
- \(n \le 200\)
- 保证计算过程中任何时刻数值都不超过 \(10^6\) 。
题解
2.1 Dijkstra 算法（适用于非负权图）
Dijkstra 算法是求解非负权图单源最短路的经典算法。其核心思想是贪心：每次从未确定最短路的顶点中选取距离源点最近的点，然后松弛它的邻接边。
算法步骤
- 初始化：
dist[source] = 0，其余顶点的dist为无穷大。用一个集合（或优先队列）来维护未访问的顶点。 - 重复以下操作，直到所有顶点都被访问：
- 从尚未确定最短路的顶点中选出
dist最小的顶点u。 - 将
u标记为已确定最短路。 - 对于
u的每个邻接顶点v，如果dist[u] + w(u,v) < dist[v]，则更新dist[v]。
复杂度分析
- 朴素实现：每次找最小
dist需要 O(V)，总复杂度 O(V²)。 - 使用优先队列（二叉堆）优化：每次插入和更新操作 O(log V)，总复杂度 O((V+E) log V)，适合稀疏图。
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,m,w[202][202],dist[202];
bool Flg[202];int main() {scanf("%d", &n);memset(w,0x3f,sizeof(w));for (int i=1;i<n;i++)for (int j=i+1;j<=n;j++)cin>>w[i][j];for (int i=1;i<=n;i++) dist[i]=INF;dist[1]=0;for (int k=1;k<n;k++) {int Min=INF,id=0;for (int i=1;i<=n;i++)if (!Flg[i] && dist[i]<Min) id=i,Min=dist[i];Flg[id]=1;for (int i=1;i<=n;i++)if (!Flg[i] && dist[i]>dist[id]+w[id][i])dist[i]=dist[id]+w[id][i];}cout<<dist[n]<<endl;return 0;
}