Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

The Postal Worker Rings Once

117.c

#include <stdio.h>
#include <string.h>
#include <limits.h>

int array[26][26];
int visited[26];

void
init(void)
{
	int i,j;
	for(i=0; i<26; i++) {
		visited[i]=0;
		for(j=0; j<26; j++) {
			array[i][j]=0;
		}
	}
}

int
min_dist(int ini, int fin)
{
	int i;
	int min;

	min=INT_MAX;

	if (ini==fin) {
		return 0;
	}
	visited[ini]=1;
	for(i=0; i<26; i++) {
		if (array[ini][i] && !visited[i]) {
			int a = array[ini][i]+min_dist(i,fin);
			if (a<min) {
				min=a;
			}
		}
	}
	visited[ini]=0;
	return min;
}

void
calc(void)
{
	int tot_len=0;
	int i,j;
	int streets;
	int ini=-1, fin=-1;

	for(i=0; i<26; i++) {
		streets=0;
		for(j=0; j<26; j++) {
			if (array[i][j]) {
				if (j>i) {
					tot_len += array[i][j];
				}
				streets++;
			}
		}
		if (streets%2) {	/* Impar */
			if (ini==-1) {
				ini=i;
			} else if (fin==-1) {
				fin=i;
			} else {
				exit(3);
			}
		}
	}
	tot_len += min_dist(ini, fin);
	printf("%d\n", tot_len);
}

int
main(void)
{
	char string[1024];

	init();
	while(1) {
		int a,b,len;
		if (scanf("%s", string)!=1) {
			break;
		}
		if (!strcmp(string, "deadend")) {
			calc();
			init();
			continue;
		}
		len = strlen(string);
		a = string[0]-'a';
		b = string[len-1]-'a';
		array[a][b] = array[b][a] = len;
	}
	exit(0);
}