prim算法 求最小生成树 1075

#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string.h>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))

int maps[105][105];

char dian[1000];

void pri(int n, int e)
{
	int disx[1000];
	int close[1000];
	for (int i = 0; i < e; i++)
	{
		disx[i] = maps[0][i];
		close[i] = 0;
	}
	for (int i = 1; i < n; i++)
	{
int min = 0xfff, k;
		for (int j = 0; j < n; j++)
		{
			if (disx[j] != 0 && disx[j] < min)
			{
				k = j;
				min = disx[j];
			}
		}

		cout << '(' << dian[close[k]] << ',' << dian[k] << ')';
		disx[k] = 0;
		for (int j = 0; j < n; j++)
		{
			if (maps[k][j] != 0 && maps[k][j] < disx[j])
			{
				disx[j] = maps[k][j];
				close[j] = k;
			}
		}
	}
}


int main()
{
	int n;
	int e;
	while (cin >> n)
	{
		cin >> e;

		scanf("%s", dian);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				maps[i][j] = i == j ? 0 : 0xfff;
			}
		}
		for (int i = 0; i < e; i++)
		{
			char from, to;
			int dis;
			cin >> from >> to >> dis;
			maps[from - 'A'][to - 'A'] = dis;
			maps[to - 'A'][from - 'A'] = dis;
		}
		pri(n, e);
	}
	return 0;
}