题目解读：

• 把城市看做节点，把路看做边。

• 很容易把题目抽象成求最小生成树的问题。

数据存储：

• 节点数小于 100，数量较少，使用邻接矩阵存储图。

算法选择：

• 节点数小于 100, 数量较少，选择 prim 算法。

算法思路：

• 需要输出路径，用 pre 数组进行存储。pre[i] 的含义是：节点 i 和节点 pre[i] 之间有一条路径。

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

const int N = 110;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边

void prim()
{
    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
    dt[1] = 0;//从 1 号节点开始生成 
    for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//每个节点一次判断
        {
            if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
                t = j;
        }

        st[t] = 1;// 选择该点

        for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
        {
            if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
            {
                dt[i] = g[t][i];//更新距离
                pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }
}

void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。

    {
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
    cin >> n >> m;//输入节点数和边数
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;//输出边的两个顶点和权重
        g[a][b] = w;//存储权重
        g[b][a] = w;//无向图，存储两次。
    }

    prim();//求最下生成树
    getPath();//输出路径
    return 0;
}

//使用邻接表
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110, M = 20010;

int h[N], e[M], ne[M], w[M],idx;



int dt[N];
int st[N];
int pre[N];
int n, m;

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

void prim()
{
    memset(dt,0x3f, sizeof(dt));
    dt[1] = 0;
    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
        {
            if(!st[j] && (t == -1 || dt[j] < dt[t]))
                t = j;
        }

        st[t] = 1;

        for(int idx = h[t]; idx != -1; idx = ne[idx])
        {
            int i = e[idx];
            if(!st[i] && dt[i] > w[idx])
            {
                pre[i] = t;
                dt[i] = w[idx];
            }
        }
    }
}

void getPath()
{
    for(int i = n; i > 1; i--)

    {
        cout << i <<" " << pre[i] << " "<< endl;
    }
}

int main()
{
    memset(h,-1, sizeof h );
    cin >> n >> m;
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
    }

    prim();
    getPath();
    return 0;
}

//k 算法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int > PII;
const int N = 110, M = 20010;

struct E
{
    int a;
    int b;
    int w;
    bool operator < (const E& e) const
    {
        return w < e.w;
    }
}e[M];

int p[N];
vector<PII> edge;
bool st[N];
int n, m;

int find(int a)
{
    if (p[a] != a)
    {
        p[a] = find(p[a]);
    }
    return p[a];
}

void getMinTree()
{
    sort(e, e + 2 * m);
    int node = 0;
    for (int i = 0; i < 2 * m; i++)
    {
        int a = e[i].a, b = e[i].b;
        int r1 = find(a), r2 = find(b);
        if (r1 != r2)
        {
            edge.push_back({ a, b });

            p[r1] = r2;
        }
    }
}

void getPath()
{
    for (auto i : edge)
    {
        cout << i.first << " " << i.second << endl;
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i <= n; i++) p[i] = i;
    for (int i = 0, j = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        e[j].a = a, e[j].b = b, e[j++].w = w;
        e[j].a = b, e[j].b = a, e[j++].w = w;
    }

    getMinTree();
    getPath();
    return 0;
}