POJ 1789 Truck History

 1 #include <string.h>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #define INF 0x0fffffff
 5 int mat[2002][2002];
 6 int N;
 7 typedef struct Code {
 8     char str[10];
 9 }Code;
10 Code codes[2002];
11 int calc(char *str1,char *str2)
12 {
13     char *p=str1,*q=str2;
14     int count=0;
15     while(*p&&*q) {
16         if((*p)!=(*q))
17             count++;
18         p++;
19         q++;
20     }
21     return count;
22 }
23 int prim()
24 {
25     int start=0;
26     bool visited[2002]={false};
27     int nearest[2002];
28     int min_cost=0;
29     int min=INF;
30     int pos;
31     int i,j;
32     for(i=0;i<N;i++)
33         nearest[i]=mat[start][i];
34     visited[start]=true;
35     nearest[start]=0;
36     for(i=1;i<N;i++) {
37         min=INF;
38         for(j=0;j<N;j++) {
39             if(!visited[j]&&nearest[j]<min) {
40                 min=nearest[j];
41                 pos=j;
42             }
43         }
44         min_cost+=min;
45         visited[pos]=true;
46         for(j=0;j<N;j++)
47             if(!visited[j]&&nearest[j]>mat[pos][j])
48                 nearest[j]=mat[pos][j];
49     }
50     return min_cost;
51 }
52 int main()
53 {
54     while(scanf("%d",&N)!=EOF) {
55         if(N==0)
56             return 0;
57         int i,j;
58         for(i=0;i<N;i++) {
59             scanf("%s",codes[i].str);
60         }
61         for(i=0;i<N;i++)
62             for(j=0;j<=i;j++)
63                 if(i==j)
64                     mat[i][j]=INF;
65                 else mat[j][i]=mat[i][j]=calc(codes[i].str,codes[j].str);
66         printf("The highest possible quality is 1/%d.\n",prim());
67     }
68     return 0;
69 }