/home/toolbox/public_html/solutions/5/567/b.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /*
16 * Author: Isaac Traxler
17 * Date: 2015-04-22
18 * Purpose:
19 * Problem: 567
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 #define MAX_SIZE 22
27 #define INFINITY 500
28 #define mx 21
29 #define MAX_TESTS 501
30
31 int a[MAX_SIZE][MAX_SIZE];
32 int caseNum = 0;
33 double avg;
34 int testCnt;
35 int test[MAX_TESTS][2];
36
37 void init()
38 {
39 /* FUNCTION init */
40 int i;
41 int j;
42
43 caseNum++;
44 for (i=0; i<MAX_SIZE; i++)
45 {
46 /* for i */
47 for (j=0; j<MAX_SIZE; j++)
48 {
49 /* for j */
50 a[i][j] = INFINITY;
51 } /* for j */
52 a[i][i] = 0; /* set digonal to distance 0 */
53 } /* for i */
54 } /* FUNCTION init */
55
56 void dump(char t[])
57 {
58 /* FUNCTION dump */
59 int i;
60 int j;
61
62 printf("%s\n", t);
63 for (i=1; i<mx; i++)
64 {
65 /* for i */
66 printf("%2d:", i);
67 for (j=1; j<mx; j++)
68 {
69 /* for j */
70 printf("%4d", a[i][j]);
71 } /* for j */
72 printf("\n");
73 } /* for i */
74 printf("\n");
75 } /* FUNCTION dump */
76
77 int getInput()
78 {
79 /* FUNCTION getInput */
80 int dataReadFlag;
81 int m;
82 int n;
83 int i;
84 int j;
85
86 dataReadFlag = 0 <= scanf(" %d ", &m);
87 if (dataReadFlag)
88 {
89 /* got a first case - process the 20 adjancency rules */
90 init();
91 for (i=1; i<20; i++)
92 {
93 /* each country */
94 for (j=0; j<m; j++)
95 {
96 /* for each connectoin to the ith country */
97 scanf(" %d ", &n);
98 a[i][n] = 1;
99 a[n][i] = 1;
100 } /* for each connectoin to the ith country */
101 /* get next count */
102 scanf(" %d ", &m);
103 } /* each country */
104 } /* got a first case - process the 20 adjancency rules */
105 testCnt = m;
106 for (i=0; i<testCnt; i++)
107 {
108 /* capture each test */
109 scanf(" %d %d ", &test[i][0], &test[i][1]);
110 } /* capture each test */
111 return (dataReadFlag);
112 } /* FUNCTION getInput */
113
114 void fw()
115 {
116 /* FUNCTION fw */
117 int i;
118 int j;
119 int k;
120
121 for (k=1; k<mx; k++)
122 {
123 /* for k */
124 for (i=1; i<mx; i++)
125 {
126 /* for i */
127 for (j=1; j<mx; j++)
128 {
129 /* for j */
130 if ((a[i][k] + a[k][j]) < a[i][j])
131 {
132 /* k is a better way to get from i to j */
133 a[i][j] = a[i][k] + a[k][j];
134 } /* k is a better way to get from i to j */
135 } /* for j */
136 } /* for i */
137 } /* for k */
138 } /* FUNCTION fw */
139
140 void process()
141 {
142 /* FUNCTION process */
143 int total;
144 int i;
145
146 DEBUG dump("Before");
147 fw();
148 DEBUG dump("After");
149 printf("Test Set #%d\n", caseNum);
150 for (i=0; i<testCnt; i++)
151 {
152 /* for each test */
153 printf("%2d to %2d: %d\n", test[i][0], test[i][1], a[test[i][0]][test[i][1]]);
154 } /* for each test */
155 printf("\n");
156 } /* FUNCTION process */
157
158 int main()
159 {
160 /* main */
161 int moreToDo;
162
163 moreToDo = getInput();
164 while (moreToDo)
165 {
166 /* while */
167 process();
168 moreToDo = getInput();
169 } /* while */
170
171 return EXIT_SUCCESS;
172 } /* main */
173