最小生成树Prim算法实现【C++】

输 入 格 式 ： {color{Violet}输入格式：} 输入格式：

∙ bullet ∙ 第一行三个数n、m、start，分别代表城市个数、道路条数、出发点（起始点）。

∙ bullet ∙ 接下来m行每行三个数a、b、c，分别表示城市a、城市b、城市a和b之间的距离。

输 出 格 式 ： {color{Violet}输出格式：} 输出格式：

∙ bullet ∙ 从起始点开始，每行输出一条选中的路径，格式为：a--b：dis，表示从a到b，距离为dis。

∙ bullet ∙ 最后一行输出总的生成代价sum_dis。

定 义 存 储 数 组 ： {color{Violet}定义存储数组：} 定义存储数组：

∙ bullet ∙ int road[max_city][max_city]，存储城市与城市之间的距离矩阵 ，初始化为无穷大。

∙ bullet ∙ int dist[max_city]，记录距离该城市最近的一个城市距离，初始化为无穷大。

∙ bullet ∙ int jilu[max_city]，存储距离该城市最近的城市编号，即jilu[s]=v表示距离城市s最近的城市是v。

∙ bullet ∙ bool visited[max_city]，记录是否已经被访问，初始化为false。

代 码 ： {color{Violet}代码：} 代码：

#include
using namespace std;

const int INF=99999999;
int road[1005][1005];
int dist[1005];
int jilu[1005];
bool visited[1005];

void prim(int n,int start)
{
    dist[start]=0;
    int res=0;
    for(int i=0;i 
 

    
     
      
       
        
         结
        
        
         果
        
        
         ：
        
       
      
      
       {color{Violet}结果：}
      
     
    结果：