算法刷题【洛谷P1359】租用游艇（最短路径Floyd算法和Dijkstra算法模板题）
2022-04-22
题目描述
长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,⋯,n 。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j) (1≤i<j≤n) 。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。
输入格式
第一行中有一个正整数 n，表示有 n 个游艇出租站。接下来的 n−1 行是一个半矩阵 r(i,j) (1≤i<j≤n) 。
输出格式
输出计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金。
输入输出样例
In 1
3
5 15
7Out 1
12这道题评级为 普及- ，十分合理。
难度不是没有（好歹是数据结构/最优路径算法，总不能给入门啊），但是这也的确就是模板题。
这道题唯一的一点小思考在于这个 半矩阵 究竟是什么玩意。我来给你用一个完整的邻接矩阵表示样例输入（0表示此路不通）：
0 5 15
? 0 7
? ? 0那么问题又来了：这些空缺如何解决？
读题：i和j的数据范围：(1≤i<j≤n)
哦。
所以这道题是一个有向图，他最终长这样（我最开始当无向图做只有66分）：
0 5 15
0 0 7
0 0 0所以最终就好给答案了，直接看代码吧（事实上就是模板 看看输入得了）
Floyd算法：
#include <bits/stdc++.h>
using namespace std;
int a[201][201];
int main() {
memset(a, 0x7f7f7f7f, sizeof(a));
int n;
cin >> n;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
cin >> a[i][j];
// a[j][i] = 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 (i == j || i == k || j == k) continue;
if (a[i][k] + a[k][j] < a[i][j]) a[i][j] = a[i][k] + a[k][j];
}
}
}
cout << a[1][n];
return 0;
}Dijkstra算法：
#include <bits/stdc++.h>
using namespace std;
int g[201][201]; // 邻接矩阵
int dis[201]; // dis[i]表示从起点到i的最短路径
bool book[201];
int main() {
memset(g, 0x7f7f7f7f, sizeof(g));
int n;
cin >> n;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
cin >> g[i][j];
}
}
book[1] = true;
for (int i = 2; i <= n; i++) {
dis[i] = g[1][i];
}
for (int i = 1; i <= n - 1; i++) {
int minnum = 0x7f7f7f7f, u;
for (int j = 1; j <= n; j++) {
if (!book[j] && dis[j] < minnum) {
// 在没有闭环的情况下，当前距离已经最短的点不可能更短了
minnum = dis[j];
u = j;
}
}
book[u] = true;
for (int v = 1; v <= n; v++) {
if (g[u][v] < 0x7f7f7f7f && dis[v] > dis[u] + g[u][v]) {
dis[v] = dis[u] + g[u][v];
}
}
}
cout << dis[n];
return 0;
}论为什么不用贝尔曼-福特？
代码麻烦啊。
一般好像只有需要判断负权回路才用到。
爷不差这点还需要费劲计算证明的时间复杂度优势