words_graph.cpp

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>


struct word {
	char str[128];
	word(char _str[128] = "") {
		strcpy(str, _str);
	}
};

bool operator<(const word& lhs, const word& rhs) {
	return strcmp(lhs.str, rhs.str) < 0;
}


struct edge {
	int from, to, dist;
	edge(int _from, int _to, int _dist) {
		from = _from;
		to = _to;
		dist = _dist;
	}
};

std::vector<int> dad;
std::vector<word> words;

bool operator<(const edge& lhs, const edge& rhs) {
	if (lhs.dist == rhs.dist) {
		return words[rhs.from] < words[lhs.from];
	}
	return lhs.dist > rhs.dist;
}

int distance(int from, int to) {
	int n = std::min(strlen(words[from].str), strlen(words[to].str));

	int dist = 0;
	for (int i = 0; i < n; ++i) {
		dist += abs(words[from].str[i] - words[to].str[i]);
	}
	return dist;
}

void prim() {
	std::priority_queue<edge> pq;
	edge curr = edge(0, 0, 0);
	pq.push(curr);

	const int n = words.size();
	dad = std::vector<int>(n, -1);

	while (!pq.empty()) {
		curr = pq.top();
		pq.pop();
		int nfrom = curr.to;

		if (dad[nfrom] != -1) {
			continue;
		}
		dad[nfrom] = curr.from;

		for (int i = nfrom + 1; i < n; ++i) {
			int nto = i;
			if (dad[nto] != -1) {
				continue;
			}
			int ndist = distance(nfrom, nto);
			pq.push(edge(nfrom, nto, ndist));
		}
	}
}

void print() {
	const int n = dad.size();
	for (int i = 1; i < n; ++i) {
		printf("%s %s\n", words[dad[i]].str, words[i].str);
	}
}

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		char buff[128];
		scanf("%s", buff);
		words.push_back(word(buff));
	}

	std::sort(words.begin(), words.end());

	prim();
	print();

	std::cin.sync();
	std::cin.get();

	return 0;
}