Uva 117 - The Postal Worker Rings Once

Problem: 117 - The Postal Worker Rings Once


Explain:
Look,

There are no node which has odd degree. So This graph has an Euler Circuit or cycle.

So the Result will be 3+3+5 = 11

There are two nodes with odd degree. So the graph has not an Euler circuit. so find the shortest path between d node to s node and this cost is add with all Euler Path. Min_Cost (d,s) = 19
and sum = 95

Total Cost = 95+19 = 114




code:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctype.h>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<algorithm>
#include<map>
#include<set>
#include<bitset>
using namespace std;

#define e 1000
#define INF 24000

int graph[30][30];
int degree[30];

void Ini(){
 int i, j;
 for(i = 0; i<27; i++) {
  for(j = 0; j<30; j++)
   graph[i][j] = INF;
  graph[i][i] = 0;
 }
}


void floyd(){
   int i,j,k;

   for( k =0 ;k<27;k++){
    for( i =0;i<27;i++){
     for(j=0;j<27;j++){
      if(graph[i][j]>graph[i][k]+graph[k][j])
       graph[i][j] = graph[i][k]+graph[k][j];
     }
    }
   }
}

void Cal(int sum){
   //find odd degree node
   int i,od1=-1,od2=-1;
   for( i =0;i<30;i++)
    if(degree[i]%2==1){
     od1 = i;
     break;
    }

   for(i=29;i>0;i--)
    if(degree[i]%2==1){
     od2 = i;
     break;
    }
    //printf("%c %c\n",od1+'a',od2+'a');
    if(od1<0 && od2<0){
        printf("%d\n",sum);
     return;
    }

    floyd();
    printf("%d\n",graph[od1][od2]+sum);
}

int main(){
  //freopen("a.in","r",stdin);
  int i=0,j=0,k=0,l=0,m=0,n=0,v=0,u=0,sum=0;
  char str[e];

  while(scanf("%s",str) == 1) {
  Ini();
  sum = 0;
  u = str[0] - 'a';
  l = strlen(str);
  sum += l;
  v = str[l-1] - 'a';
  graph[u][v] = graph[v][u] = l;
  degree[u]++;
  degree[v]++;
  while(1) {
   scanf("%s",str);
   if(!strcmp(str, "deadend"))
    break;
   u = str[0] - 'a';
   l = strlen(str);
   v = str[l-1] - 'a';
   graph[u][v] = graph[v][u] = l;
   sum +=l;
   degree[u]++;
   degree[v]++;
  }

  Cal(sum);

  for(int i = 0; i<30; i++)
   degree[i] = 0;

 }
 return 0;
}