长江游艇俱乐部在长江上设置了 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
n\le 200n≤200，保证计算过程中任何时刻数值都不超过 10^6106。
原题链接->传送门
依次更新从1到每个节点的最短距离，最后求出到最后一个节点n的距离，开始敲完代码测试题目给的数据结果倒是对了，但我感觉交上去应该不会过，自己画了图换了数据果然有问题，后面再改，换了好多组数据测都没什么问题了，但是交上去只有42分。
下面是错误代码和测试数据：
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 5;
const int N = 205;//n<=200
int vis[N];//节点访问标记数组
int low[N];//记录最短路径的数组
int Map[N][N];//图的储存数组
int n;//游艇出租站数量
int Dijkstra(int begin, int end)//dijkstra算法,传入起点和终点
{
// 初始化
for (int i = 1; i <= n; i++)
{
low[i] = inf;
vis[i] = false;//初始化每个节点的标记为空
}
low[begin] = 0;
vis[begin] = true;//源节点
for (int i = 2; i <= n; i++)
{
low[i] = Map[begin][i];//初始化最短距离为直接距离，这里是最少租金
}
/*-------------------------------------------------------------------------------------------------*/
for (int i = 2; i <= n; i++)
{
// 找到一个最短的，并且记录下来
int Min = inf, idx = -1;//初始化
for (int j = i; j <= n; j++)
{
if (low[j] < Min)
{
Min = low[j];
idx = j;
}
}
vis[idx] = true;//查找未访问的low[ i ]的最小值，记录最小下标index并记m_len=low[ index ]，
//标记已访问visit[ index ] = true,直到所有visit数组均为true,low[ end ]为所求值
cout << "i=" << i << " Min=" << Min << " idx=" << idx << endl ;
// 更新
for (int j = 2; j <= n; j++)
{
if (low[j] > Min + Map[idx][j])
{
printf("Map[%d][%d] = %d\n",idx,j,Map[idx][j]);
low[j] = Min + Map[idx][j];
vis[false];
}
cout << "low[" << j << "]=" << low[j] << endl ;
}
}
/*-------------------------------------------------------------------------------------------------*/
return low[end];//返回最少租金
}
int main()
{
cin >> n ;//n个游艇出租站
for(int i = 1 ; i <= n ; i++)//将Map数组初始化为0
{
for(int j = 1 ; j<= n ; j++)
{
Map[i][j] = 0 ;
}
}
for (int i = 1 ; i <= n-1 ; i++)//n-1行半矩阵
{
for(int j = i+1; j <= n ; j++)
{
cin >> Map[i][j] ;//代表第i个游艇站到第j个游艇站的租金
}
}
/*for (int i = 1 ; i <= n-1 ; i++)//n-1行半矩阵
{
for(int j = i+1; j <= n ; j++)
{
printf("第%d个游艇站到第%d个游艇站的租金=",i,j);
cout << Map[i][j] <<endl;//代表第i个游艇站到第j个游艇站的租金
}
}*/
cout << Dijkstra(1,n) ;//游艇出租站 1 到游艇出租站 n 所需的最少租金
return 0;
}
/*
测试数据1：
3
5 15
7
结果1：12
测试数据2:
5
1 4 6 20
7 6 10
3 7
2
结果2:
8
测试数据3：
5
1 4 8 20
7 6 10
3 7
2
结果3：
9
测试数据4：
5
2 4 8 20
7 6 10
3 7
2
结果4：
9
*/ //用了标记数组后的，更离谱，只有32分
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 5;
const int N = 205;//n<=200
int vis[N];//节点访问标记数组
int low[N];//记录最短路径的数组
int Map[N][N];//图的储存数组
int n;//游艇出租站数量
int Dijkstra(int begin, int end)//dijkstra算法,传入起点和终点
{
// 初始化
for (int i = 1; i <= n; i++)
{
low[i] = inf;
vis[i] = false;//初始化每个节点的标记为空
}
low[begin] = 0;
vis[begin] = true;//源节点
for (int i = 2; i <= n; i++)
{
low[i] = Map[begin][i];//初始化最短距离为直接距离，这里是最少租金
}
/*-------------------------------------------------------------------------------------------------*/
for (int i = 2; i <= n; i++)
{
// 找到一个最短的，并且记录下来
int Min = inf, idx = -1;//初始化
for (int j = i; j <= n; j++)
{
if (!vis[j] && low[j] < Min)
{
Min = low[j];
idx = j;
}
}
vis[idx] = true;//查找未访问的low[ i ]的最小值，记录最小下标index并记m_len=low[ index ]，
//标记已访问visit[ index ] = true,直到所有visit数组均为true,low[ end ]为所求值
//cout << "i=" << i << " Min=" << Min << " idx=" << idx << endl ;
//更新
for (int j = 2; j <= n; j++)
{
if (low[j] > Min + Map[idx][j])
{
//printf("Map[%d][%d] = %d\n",idx,j,Map[idx][j]);
low[j] = Min + Map[idx][j];
//vis[false];
}
//cout << "low[" << j << "]=" << low[j] << endl ;
}
}
/*-------------------------------------------------------------------------------------------------*/
return low[end];//返回最少租金
}
int main()
{
cin >> n ;//n个游艇出租站
for(int i = 1 ; i <= n ; i++)//将Map数组初始化为0
{
for(int j = 1 ; j<= n ; j++)
{
Map[i][j] = 0 ;
}
}
for (int i = 1 ; i <= n-1 ; i++)//n-1行半矩阵
{
for(int j = i+1; j <= n ; j++)
{
cin >> Map[i][j] ;//代表第i个游艇站到第j个游艇站的租金
}
}
/*for (int i = 1 ; i <= n-1 ; i++)//n-1行半矩阵
{
for(int j = i+1; j <= n ; j++)
{
printf("第%d个游艇站到第%d个游艇站的租金=",i,j);
cout << Map[i][j] <<endl;//代表第i个游艇站到第j个游艇站的租金
}
}*/
cout << Dijkstra(1,n) ;//游艇出租站 1 到游艇出租站 n 所需的最少租金
return 0;
}呜呜呜，实在是改不动了，小花看完我的代码帮我改了一些细节，先不说了，我要肝题了555~，今晚回家才发现题组明早截至，一整个愣住
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 5;
const int N = 205;//n<=200
int vis[N];//节点访问标记数组
int low[N];//记录最短路径的数组
int Map[N][N];//图的储存数组
int n;//游艇出租站数量
int Dijkstra(int begin, int end)//dijkstra算法,传入起点和终点
{
// 初始化
for (int i = 1; i <= n; i++)
{
low[i] = inf;
vis[i] = false;//初始化每个节点的标记为空
}
low[begin] = 0;
vis[begin] = true;//源节点
for (int i = 1; i <= n; i++)
{
low[i] = Map[begin][i];//初始化最短距离为直接距离，这里是最少租金
}
for (int i = 1; i <= n; i++)
{
// 找到一个最短的，并且记录下来
int Min = inf, idx = -1;//初始化
for (int j = 1; j <= n; j++)
{
if (!vis[j] && low[j] < Min)
{
Min = low[j];
idx = j;
}
}
vis[idx] = true;
if(idx == -1) //不能连接
break;
for (int j = 1; j <= n; j++)
{
if (!vis[j] && (low[j] > Min + Map[idx][j]))
{
low[j] = Min + Map[idx][j];
}
}
}
return low[end];
}
int main()
{
cin >> n ;//n个游艇出租站
for(int i = 0 ; i <= n ; i++)//将Map数组初始化为0
{
for(int j = 0 ; j<= n ; j++)
{
if(i==j)
Map[i][j] = 0 ;
else
Map[i][j] = inf;
}
}
for (int i = 1 ; i <= n-1 ; i++)//n-1行半矩阵
{
for(int j = i+1; j <= n ; j++)
{
cin >> Map[i][j] ;//代表第i个游艇站到第j个游艇站的租金
}
}
cout << Dijkstra(1,n);
return 0;
}