乡村卫生所选址

深碍√TFBOYSˉ_ 2023-07-07 05:54 2阅读 0赞

二叉树相关知识

#include <iostream>
    #define N 100
    using namespace std;
    void main()
    {
    	char v[N] = { 0 };//存放顶点字母
    	int n;
    	int e[N][N] = { 0 };//存放两地之间的距离
    	cout << "输入顶点个数" << endl;
    	cin >> n;
    	cout << "输入顶点字母" << endl;
    	for (int i = 0; i < n; i++)
    		cin >> v[i];
    	cout << "输入两地之间的距离" << endl;
    
    	//输入矩阵
    	for (int i = 0; i < n; i++)
    		for (int j = i + 1; j < n; j++)
    		{
    			cout << "输入" << v[i] << "到" << v[j] << "之间的距离（没有直接路径请输入‘100’）" << endl;
    			cin >> e[i][j];
    			e[j][i] = e[i][j];
    		}
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < n; j++)
    		{
    			if (i == j)
    				e[i][j] = 0;
    		}
    	cout << endl;
    	//最短路径矩阵
    	cout << "最短距离矩阵为：" << endl;
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j < n; j++)
    		{
    			for (int k = 0; k < n; k++)
    			{
    
    				if (e[i][j] > e[i][k] + e[k][j])
    
    				{
    					e[i][j] = e[i][k] + e[k][j];
    
    				}
    
    				if (i == j)
    					e[i][j] = 0;
    			}
    			cout << " " << e[i][j] << " ";
    
    		}
    		cout << endl;
    		cout << endl;
    
    	}
    	//输出卫生所所在村庄
    	char M;
    	int min = N;
    	//int m[sizeof(e[n][n])]={N};
    	int y;
    	//int sum=0;
    	for (int i = 0; i < n; i++)
    	{
    		int sum = 0;
    		for (int j = 0; j < n; j++)
    		{
    			sum += e[i][j];
    		}
    
    		if (min > sum)
    		{
    
    			min = sum;
    			M = v[i];
    			y = i;
    		}
    
    	}
    	cout << "卫生所应建在" << M << "地" << endl;
    	//输出卫生所到各点的距离
    
    	for (int i = 0; i < n; i++)
    		if (M != v[i])
    		{
    			cout << M << "地距" << v[i] << "地的距离为：";
    			cout << e[i][y] << endl;
    		}
    
    	//输出最短路径
    	/*int s=0;
    	for(i=0;i<n;i++)
    	{
    	s+=e[i][y];
    	}
    	cout<<endl;*/
    	cout << "最短路径长度为：" << min << endl;
    }