@[xiaoxiaoxia](/user/677127) 我让 ChatGPT 调试了一下，内容如下……感觉不靠谱。但是还是要尝试一下吧……
（问了两次）
# 第一次：
这段代码的问题在于在使用Dijkstra算法时没有正确初始化vis数组。在dijkstra函数中，应该在每次找到最小距离的节点后，将其标记为已访问，即vis[u] = 1。这样可以确保每个节点都会被遍历到，并且不会重复访问。
以下是修改后的代码：
```cpp
#include<iostream>
#define inf 0x3f3f3f3f3f
using namespace std;
int n;
int mp[205][205];
int dis[205];
int vis[205];
void init()
{
for (int i = 0; i < 205; i++)
{
dis[i] = inf;
for (int j = 0; j < 205; j++)
{
mp[i][j] = inf;
if (i == j)
{
mp[i][j] = 0;
}
}
}
}
void dijkstra(int x)
{
dis[x] = 0; // 将起始点的距离初始化为0
for (int i = 0; i < n; i++)
{
int minn = inf, u = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && dis[j] < minn)
{
minn = dis[j];
u = j;
}
}
vis[u] = 1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && dis[u] + mp[u][j] < dis[j])
{
dis[j] = dis[u] + mp[u][j];
}
}
}
}
int main()
{
cin >> n;
init();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
cin >> mp[i][j];
mp[j][i] = mp[i][j];
}
}
dijkstra(0);
cout << dis[n-1] << endl;
return 0;
}
```
此外，还需要确保输入的图是连通的，如果输入的图不连通，则可能导致无法到达终点，此时输出的dis[n-1]将是初始值inf。
# 第二次：
这段代码存在一些问题，以下是修改后的代码：
```cpp
#include<iostream>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
int n;
int mp[205][205];
int dis[205];
bool vis[205];
void init()
{
memset(dis, inf, sizeof(dis));
memset(vis, false, sizeof(vis));
for (int i = 0; i < 205; i++)
{
for (int j = 0; j < 205; j++)
{
mp[i][j] = inf;
if (i == j)
{
mp[i][j] = 0;
}
}
}
}
void dijkstra(int x)
{
dis[x] = 0;
for (int i = 0; i < n; i++)
{
int minn = inf, u = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && dis[j] < minn)
{
minn = dis[j];
u = j;
}
}
if (u == -1)
{
break;
}
vis[u] = true;
for (int j = 0; j < n; j++)
{
if (!vis[j] && dis[u] + mp[u][j] < dis[j])
{
dis[j] = dis[u] + mp[u][j];
}
}
}
}
int main()
{
cin >> n;
init();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
cin >> mp[i][j];
mp[j][i] = mp[i][j];
}
}
dijkstra(0);
cout << dis[n-1] << endl;
return 0;
}
```
修改的主要内容包括：
将vis数组的类型从int改为bool，用于标记节点是否已经访问过。
在init()函数中，使用memset()函数将dis数组和vis数组初始化为初始值。
在dijkstra()函数中，添加了一个判断条件，当找不到未访问节点时，直接退出循环。
在main()函数中，将dis[0]的初始值设置为0，因为起始节点为0。
修改了dijkstra()函数中的一处错误，将vis[u] = 1;修改为vis[u] = true;。
by junhaowang @ 2023-11-29 20:02:20
@[junhaowang](/user/562521) 不要让GPT写代码，它只会写出一堆勾石qwq
~~它连P1001都A不掉~~
by wjy959 @ 2023-12-26 13:41:36
@[xiaoxiaoxia](/user/677127) 这是个**有向图**，不需要mp[j][i] = mp[i][j];
by wjy959 @ 2023-12-26 13:49:14
@[wjy959](/user/520171) 确实……深有同感
by junhaowang @ 2023-12-27 19:02:29