OJ Board

Code: Select all

//117 The Postal Worker rings once
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
const char dead[]="deadend";
#define N 40
#define LEN 1000
#define inf 99999999
int edge[N][N],degree[N];
int main(){
	//freopen("a.in","r",stdin);
	char st[LEN];
	int len;
	int _wer=0,sum=0,odd1,odd2,x,y;
	while(1){
		_wer=0;
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++) 
				edge[i][j]=inf;
		for(int i=0;i<N;i++) degree[i]=0;
		while(cin>>st){
			_wer=1;
			if(strcmp(st,dead)==0) break;
			len=strlen(st);
			x=st[0]-'a';y=st[len-1]-'a';
			if (edge[x][y]>len){
			edge[x][y]=len;
			edge[y][x]=len;
			}
			degree[x]++;
			degree[y]++;
			sum+=len;
		}
		if(_wer==0) break;
		int q;odd1=-1;odd2=-1;
		for(q=0;q<N;q++) if (degree[q]%2!=0){odd1=q;q++;break;}
		for(;q<N;q++) if(degree[q]%2!=0){odd2=q;break;}

		if(odd1!=-1 && odd2!=-1)
		{
			assert(odd1!=odd2);
			for(int i=0;i<N;i++) edge[i][i]=0;
			for(int k=0;k<N;k++){
				for(int i=0;i<N;i++){
					for(int j=0;j<N;j++){
						if (edge[i][k]+edge[k][j]<edge[i][j])
							edge[i][j]=edge[i][k]+edge[k][j];
					}
				}
			}
		cout<<sum+edge[odd1][odd2]<<endl;
		}
		else cout<<sum<<endl;
	}
	return 0;
}

Code: Select all

[#include <iostream>
#include <string>
#include <fstream>

using namespace std;



const int Max=1000000; 
const int mx=10000;
const int bound=27;

int cost[bound][bound]={Max};
int sw[mx]={-1};
int i,j,k,count=0;

int dijkstra(int first,int last){
	sw[first]=1;
	int cur;
	int min=Max;

	for(j=1;j<bound;j++){
		min=Max;
		for(k=1;k<bound;k++){
			if(!sw[k]){
				if(cost[first][k]<min){ min=cost[first][k]; cur=k;}
			}
		}
		sw[cur]=1;

		for(i=0;i<bound;i++){
			if(!sw[i] && i!=first && i!=cur){
				if(cost[first][i]>cost[first][cur]+cost[cur][i]){
					cost[first][i]=cost[first][cur]+cost[cur][i];
				}
			}
		}
		if(cur==last) break;
	}
	return cost[first][last];
}


void main(){
		
	for(i=0;i<bound;i++){
		for(j=0;j<bound;j++){
			cost[i][j]=Max;
		}
	}
	
//	ifstream cin("117.in");

	char temp[1000];
	int firstNode,lastNode;
	int w=0;
	int l=0;

	while(1){
		cin>>temp;
		if(!strcmp(temp,"deadend")){
			w=0;
			firstNode=-1;
			lastNode=-1;
			int sumEdges=0;

			for(i=0;i<bound;i++){
				count=0;
				for(j=0;j<bound;j++){
					if(cost[i][j]!=Max){
						sumEdges+=cost[i][j];
						count++;
					}
				}
				if((count%2)){
					if(!w){
						firstNode=i;
						w=1;
					}
					else lastNode=i;
				}							
			}
			
			sumEdge/=2;
			
			if(firstNode!=-1)	sumEdges+=dijkstra(firstNode,lastNode);

			cout<<sumEdges<<endl;

			for(i=0;i<bound;i++){
				sw[i]=0;
				for(j=0;j<bound;j++){
					cost[i][j]=Max;
				}
			}
			continue;
		}
		else if(cin.eof()) break;
		int length=strlen(temp);
		l+=length;
		cost[temp[0]-'a'][temp[length-1]-'a']=length;
		cost[temp[length-1]-'a'][temp[0]-'a']=length;
		sw[temp[0]-'a']=0;
		sw[temp[length-1]-'a']=0;		
	}
}