无向图最短路径C++实现，考虑边的权重，不用stl容器实现

以下是无向图最短路径的C++实现，使用邻接矩阵存储图，不使用STL容器：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100;  // 最大点数
const int INF = 0x3f3f3f3f;  // 无穷大

int n, m;  // 点数、边数
int map[MAXN][MAXN];  // 邻接矩阵表示图
int dis[MAXN];  // 距离数组
bool vis[MAXN];  // 标记数组

void dijkstra(int start) {
    memset(vis, 0, sizeof(vis));  // 初始化标记数组
    for (int i = 1; i <= n; ++i) {
        dis[i] = map[start][i];  // 初始化距离数组
    }
    vis[start] = true;  // 标记起点
    for (int i = 1; i < n; ++i) {
        int min_dis = INF, min_pos = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && dis[j] < min_dis) {  // 找到距离最小的未标记点
                min_dis = dis[j];
                min_pos = j;
            }
        }
        if (min_pos == -1) return;  // 所有点均不连通
        vis[min_pos] = true;  // 标记该点
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && dis[j] > dis[min_pos] + map[min_pos][j]) {  // 更新距离数组
                dis[j] = dis[min_pos] + map[min_pos][j];
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(map, INF, sizeof(map));  // 初始化邻接矩阵
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        map[u][v] = map[v][u] = w;  // 无向图
    }
    int start;
    cin >> start;
    dijkstra(start);
    for (int i = 1; i <= n; ++i) {
        cout << dis[i] << ' ';
    }
    cout << endl;
    return 0;
}

其中，dijkstra函数实现了Dijkstra算法求最短路径，其时间复杂度为O(n^2)。对于稠密图，邻接矩阵存储方式可以有效减少空间浪费。