1164.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1164 on 2005-11-10 at 20:25:14 */ 
#include <cstdio>
#include <cstring>

const int MAX = 32;
const int L_MAX = 1024;
const int INFINITE = 5000;

int edge[MAX][MAX];
int ideg[MAX];

int Dijkstra(int, int);

int main()
{
	int total, odd[2];
	char line[L_MAX];
	int i, j, k, l;
	
	while(true) {
		for(i = 0; i <MAX; i++) {
			for(j = 0; j < MAX; j++) {
				edge[i][j] = INFINITE;
			}
		}
		memset(ideg, 0, sizeof(ideg));
		total = 0;
		while(true) {
			if(gets(line) == NULL) {
				return 0;
			} else if(!strcmp(line, "deadend")) {
				break;
			} else {
				l = strlen(line);
				edge[line[0]-'a'][line[l-1]-'a'] = edge[line[l-1]-'a'][line[0]-'a'] = l;
				total += l;
				ideg[line[0]-'a']++;
				ideg[line[l-1]-'a']++;
			}
		}
		k = 0;
		for(i = 0; i < MAX; i++) {
			if(ideg[i] % 2 == 1) {
				odd[k++] = i;
			}
		}
		if(k != 0) {
			total += Dijkstra(odd[0], odd[1]);
		}
		printf("%d\n", total);
	}
	
	return 0;
}

int Dijkstra(int src, int dis)
{
	int d[MAX], min, mini;
	int i, j;
	bool visit[MAX] = {false};
	
	for(i = 0; i < MAX; i++) {
		d[i] = INFINITE;
	}
	d[src] = 0;
	for(i = 0; i < MAX; i++) {
		min = INFINITE;
		mini = -1;
		for(j = 0; j < MAX; j++) {
			if(!visit[j] && min > d[j]) {
				min = d[j];
				mini = j;
			}
		}
		if(mini == -1 || mini == dis) {
			break;
		} else {
			visit[mini] = true;
			for(j = 0; j < MAX; j++) {
				if(d[mini] + edge[mini][j] < d[j]) {
					d[j] = d[mini] + edge[mini][j];
				}
			}
		}
	}
	
	return d[dis];
}