文件目录

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int f[105][105], n, e, a, b, c;
bool vis[105]; // 标记已访问
int fat[105];  // 父亲节点
struct node
{
    int to, w;
    bool operator<(const node &b) const
    {
        return w > b.w; // 从小到大，小顶堆
    }
};
void prim()
{
    // 优先队列
    priority_queue<node> p;
    // 任意点入队（默认第一个点）
    p.push({1, 0});
    // 只要队不为空
    while (!p.empty())
    {
        // 取队头
        node u = p.top();
        p.pop();
        // 判断目标是否访问过，continve
        if (vis[u.to])
            continue;
        // 标记
        vis[u.to] = true;
        if (u.to != fat[u.to])
            cout << fat[u.to] << " " << u.to << "\n";
        // 枚举所有未访问节点
        for (int i = 1; i <= n; i++)
        {
            // 如果可以到达，加入优先队列
            if (!vis[i] && f[u.to][i] < f[0][0])
            {
                p.push({i, f[u.to][i]});
                // 更新最短距离
                if (f[u.to][i] < f[fat[i]][i])
                    fat[i] = u.to;
            }
        }
    }
}
int main()
{
    memset(f, 0x3f, sizeof(f));
    cin >> n >> e;
    for (int i = 1; i <= e; i++)
    {
        cin >> a >> b >> c;
        f[a][b] = f[b][a] = c;
    }
    for (int i = 1; i <= n; i++)
        fat[i] = i; // 初始父亲为自己
    prim();
    return 0;
}