UVa 117 - The Postal Worker Rings Once

// UVa 117 - The Postal Worker Rings Once

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

int lnk['z' + 1]['z' + 1], oo;

int dijkstra(int start, int end) {
	bool taken['z' + 1];
	int dist['z' + 1];
	memset(taken, false, sizeof(taken));
	memset(dist, 127, sizeof(dist));
	dist[start] = 0;
	int next = start;
	while (next != end && next != -1) {
		taken[next] = true;
		for (char c = 'a'; c <= 'z'; c++)
			if (dist[c] > dist[next] + lnk[next][c])
				dist[c] = dist[next] + lnk[next][c];
		next = -1;
		for (char c = 'a'; c <= 'z'; c++) {
			if (!taken[c] && (next == -1 || dist[c] < dist[next]))
				next = c;
		}
	}
	return dist[end];
}

int main() {
	string st;
	while (getline(cin, st)) {
		int sol = 0;
		memset(lnk, 127, sizeof(lnk));
		oo = lnk[0][0];
		int degree['z' + 1];
		memset(degree, 0, sizeof(degree));
		while (st != "deadend") {
			char a = st[0], b = st[st.length() - 1];
			lnk[a][b] = lnk[b][a] = st.length();
			degree[a]++;
			degree[b]++;
			sol += st.length();
			getline(cin, st);
		}
		int start, end;
		bool odd = false;
		for (int c = 'a'; c <= 'z'; c++) {
			if (degree[c] & 1) {
				start = end;
				end = c;
				odd = true;
			}
		}
		if (odd)
			sol += dijkstra(start, end);
		cout << sol << endl;
	}
	return 0;
}