思路: 简单的最小生成树问题, 题目条件 n <= 100, 是稠密图,考虑用prim算法. 由于题目要求输出 哪两个城市建路(也就是最小生成树边的顶点). min1 数组表示这个点离集合中哪个点最近. 那么答案就是{min1[i],i}

#include <iostream>
#include<stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
using namespace std;
const int N = 100 + 10;
int n,e;
int g[N][N],min1[N];
int dist[N],idx;
bool st[N];
typedef pair<int ,int> pii;
pii path[1000 -1];
bool prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 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;
        }
        if(i && dist[t] == 0x3f3f3f3f) return false;
        if(i)
        {
            res += dist[t];
            path[idx ++] = {min1[t],t};          //此时t是要加入的点,因此 需要找到t离集合中哪个点最近
        }                                        // 并把它合成一个pair

        for(int j = 1; j <= n; j++)
            {
                if(dist[j] > g[t][j])
                {
                    dist[j] = g[t][j];
                    min1[j] = t;           // 来记录此时 最短距离的时候,顶点j离集合中路径最短的点是t
                }
            }
        st[t] = true;
    }
    return true;
}

int main()
{
    cin >> n >> e;
    memset(g, 0x3f,sizeof g);
    for(int i = 0; i < e; i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b] , c);
    }
   prim();
   for(int i = 0; i < idx; i++)
   {
       int a = path[i].first ,b = path[i].second;
       cout << a << " " << b <<endl;
   }

}