不用stl实现上述代码
时间: 2023-07-24 22:10:56 浏览: 43
好的,以下是不使用 STL 的代码实现:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 400010;
int n, m, s, t;
int h[N], e[M], ne[M], w[M], idx; // 邻接表存图
int dist[N]; // 存储起点到各个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist); // 初始化 dist 数组,全部赋为 INF
dist[s] = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1; // 在还未确定最短路的点中,寻找距离起点最近的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true; // 确定一个点的最短路
for (int j = h[t]; ~j; j = ne[j]) // 用刚确定的点更新其他点的距离
{
int k = e[j];
if (dist[k] > dist[t] + w[j])
dist[k] = dist[t] + w[j];
}
}
}
int main()
{
cin >> n >> m >> s >> t;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dijkstra();
cout << dist[t] << endl;
return 0;
}
```
这里的大部分代码和 STL 版本的 Dijkstra 算法实现是相同的,主要区别在于堆优化的部分,改为了暴力寻找距离起点最近的点。因为这样的写法每次需要遍历所有未确定最短路的点,因此时间复杂度为 O(n^2),而不是 O(mlogn)。