/home/toolbox/public_html/solutions/5/567/a.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
30 int a[MAX_SIZE][MAX_SIZE];
31 int caseNum = 0;
32 double avg;
33 int testCnt;
34
35 void init()
36 {
37 /* FUNCTION init */
38 int i;
39 int j;
40
41 caseNum++;
42 for (i=0; i<MAX_SIZE; i++)
43 {
44 /* for i */
45 for (j=0; j<MAX_SIZE; j++)
46 {
47 /* for j */
48 a[i][j] = INFINITY;
49 } /* for j */
50 a[i][i] = 0; /* set digonal to distance 0 */
51 } /* for i */
52 } /* FUNCTION init */
53
54 void dump(char t[])
55 {
56 /* FUNCTION dump */
57 int i;
58 int j;
59
60 printf("%s\n", t);
61 for (i=1; i<mx; i++)
62 {
63 /* for i */
64 printf("%2d:", i);
65 for (j=1; j<mx; j++)
66 {
67 /* for j */
68 printf("%4d", a[i][j]);
69 } /* for j */
70 printf("\n");
71 } /* for i */
72 printf("\n");
73 } /* FUNCTION dump */
74
75 int getInput()
76 {
77 /* FUNCTION getInput */
78 int dataReadFlag;
79 int m;
80 int n;
81 int i;
82 int j;
83
84 dataReadFlag = 0 <= scanf(" %d ", &m);
85 if (dataReadFlag)
86 {
87 /* got a first case - process the 20 adjancency rules */
88 init();
89 for (i=1; i<20; i++)
90 {
91 /* each country */
92 for (j=0; j<m; j++)
93 {
94 /* for each connectoin to the ith country */
95 scanf(" %d ", &n);
96 a[i][n] = 1;
97 a[n][i] = 1;
98 } /* for each connectoin to the ith country */
99 /* get next count */
100 scanf(" %d ", &m);
101 } /* each country */
102 } /* got a first case - process the 20 adjancency rules */
103 testCnt = m;
104 return (dataReadFlag);
105 } /* FUNCTION getInput */
106
107 void fw()
108 {
109 /* FUNCTION fw */
110 int i;
111 int j;
112 int k;
113
114 for (k=1; k<mx; k++)
115 {
116 /* for k */
117 for (i=1; i<mx; i++)
118 {
119 /* for i */
120 for (j=1; j<mx; j++)
121 {
122 /* for j */
123 if ((a[i][k] + a[k][j]) < a[i][j])
124 {
125 /* k is a better way to get from i to j */
126 a[i][j] = a[i][k] + a[k][j];
127 } /* k is a better way to get from i to j */
128 } /* for j */
129 } /* for i */
130 } /* for k */
131 } /* FUNCTION fw */
132
133 void process()
134 {
135 /* FUNCTION process */
136 int total;
137 int i;
138 int frm;
139 int to;
140
141 DEBUG dump("Before");
142 fw();
143 DEBUG dump("After");
144 printf("Test Set #%d\n", caseNum);
145 for (i=0; i<testCnt; i++)
146 {
147 /* for each test */
148 scanf(" %d %d ", &frm, &to);
149 printf("%2d to %2d: %d\n", frm, to, a[frm][to]);
150 } /* for each test */
151 printf("\n");
152 } /* FUNCTION process */
153
154 int main()
155 {
156 /* main */
157 int moreToDo;
158
159 moreToDo = getInput();
160 while (moreToDo)
161 {
162 /* while */
163 process();
164 moreToDo = getInput();
165 } /* while */
166
167 return EXIT_SUCCESS;
168 } /* main */
169