用c++实现第一个算法，不用stl容器实现

好的，下面给出使用 C++ 实现 Dijkstra 算法的代码，不使用 STL 容器实现：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010;

int n, m, s, t;
bool st[N];
int h[N], e[N], w[N], ne[N], idx;
int d[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[s] = 0;
    
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || d[t] > d[j]))
                t = j;
                
        st[t] = true;
        
        for (int j = h[t]; j != -1; j = ne[j])
        {
            int k = e[j];
            if (d[k] > d[t] + w[j])
                d[k] = d[t] + w[j];
        }
    }
    
    return d[t];
}

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);
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}

这里使用邻接表存储图，数组 st 表示节点是否已经加入集合 S，h 数组存储每个节点的出边链表，d 数组表示 s 到各个节点的距离。在每一次循环中，从集合 V-S 中找到距离 s 最近的节点 u，将 u 加入集合 S，然后更新与 u 相邻的节点的距离。最后返回 d[t] 即可。