dijkstra算法95分求助

P2683 小岛

这段代码存在一些问题: 在 dijkstra 函数中,没有考虑到边权可能为负数的情况。迪杰斯特拉算法不适用于存在负权边的情况。应该使用 Bellman-Ford 算法或 Floyd-Warshall 算法处理带负权边的情况。 在 main 函数中,没有初始化 mindis 数组,导致在循环输出结果时可能输出垃圾值。 在 main 函数中,没有对图中不存在的边进行处理,即没有将不存在的边初始化为一个非负值,而是初始化为 -1。这会导致在查询时无法正确判断两个节点之间是否存在边。 为了修复这些问题,你可以考虑使用适合处理负权边的算法,并对输入的图进行适当的初始化。 下面是修复后的代码: ``` #include<bits/stdc++.h> using namespace std; const int inf = 0x7fffff; int dis[101], check[101]; int graph[101][101]; int n, m; void dijkstra(int s) { for (int i = 1; i <= n; i++) { dis[i] = inf; check[i] = 0; } dis[s] = 0; for (int i = 1; i <= n; i++) { int minn = inf, minx; for (int j = 1; j <= n; j++) { if (dis[j] < minn && check[j] == 0) { minn = dis[j]; minx = j; } } check[minx] = 1; for (int j = 1; j <= n; j++) { if (graph[minx][j] != -1 && minn + graph[minx][j] < dis[j]) { dis[j] = minn + graph[minx][j]; } } } } int main() { int q, k = 0; int u, v; int mindis[5001]; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { graph[i][j] = (i == j) ? 0 : -1; // 初始化,自己到自己为0,其它为-1 } } for (int i = 0; i < m; i++) { scanf("%d", &q); if (q == 1) { int e; scanf("%d%d%d", &u, &v, &e); if (graph[u][v] > e || graph[u][v] == -1) { graph[u][v] = e; graph[v][u] = e; } } else if (q == 0) { scanf("%d%d", &u, &v); dijkstra(u); if (dis[v] == inf) mindis[k++] = -1; else mindis[k++] = dis[v]; } } for (int i = 0; i < k; i++) { printf("%d\n", mindis[i]); } return 0; } ``` 这个修复后的代码将初始化不存在的边为 -1,并在 dijkstra 函数中处理了边权可能为负数的情况。
by 11514zbs @ 2024-03-05 06:54:48


@[11514zbs](/user/1125106) 好的 谢谢您
by akldjdj @ 2024-03-06 19:17:44


|