Towards the Capital

Step 1. Let's call $\text{map} \in \mathbb{N}^{98 \times 2}$ the input file. Let's call $M \in \mathbb{N}^{100 \times 100}$ a matrix in which $m_{ij} \in M$ is the distance from city $i$ to city $j$ . It's clear that $m_{ij}=m_{ji}$ . So, each row of $\text{map}$ represents cities that are directly connected. For example,

$\displaystyle \text{map}(1,:)=[1\hspace{5pt} 2] \hspace{5pt} \Longrightarrow \hspace{5pt} m_{1 2}=m_{2 1}=1$

In other terms, I'm giving value $1$ to $m_{ij}$ if $[i \hspace{5pt} j]$ is a row of $\text{map}$ . We can continue this process for all $98$ rows of $\text{map}$ . For the sake of coherence, $m_{ij}=0$ if $i=j$ .

Now, let's look at $M(1,:)$ . We see that $m_{12}=m_{14}=m_{15}=m_{19}=m_{1,11 }=m_{1,12}=m_{1,42}=m_{1,48}=1)$ . This means that $1$ is directly connected with $2, 4, 5, 9 ...$ and so on. Let's look at $M(2,:)$ . We'll find that $m_{21}=m_{23}=m_{2,19}=m_{2,39}=m_{2,77 }=1)$ . This means that $2$ is directly connected with $1$ (we already knew that) $3,19,39$ and $77$ . But this means that city $1$ has distance $2$ from cities $3,19,39$ , namely

$m_{13}=m_{1,19}=m_{1,39}=m_{1,77}=2$ .

So, this is the algorithm main structure after Step 1 :

Step 2.

• Let be $m_{ij}=d$ . We consider $M(i,:)$ . We put in an array called $\text{connection}$ every $m_{ij}$ such that $m_{ij}=d$ . Let's call $c$ elements of $\text{connection}$ .
• We go in $M(c,:)$ for each $c \in \text{connection}$ . We put in an array called $\text{connectionII}$ every $m_{c,k}$ such that $m_{c,k}=1$ . Let's call $cII$ elements of $\text{connectionII}$
• We come back in $M(i,:)$ and write $m_{i,cII}=d+1$ for each $cII \in \text{connectionII}$

We do this procedure for $1 \leq i \leq 100$ . After $i=100$ we check if there are any $m_{ij}=0 \in M$ for $i \neq j$ . If there aren't any, Step 2. ends. If there are still some, we repeat Step 2. for $d=d+1$ .

At the end we'll have a matrix $M$ in which only the elements on the diagonal are zero. Eventually we find the maximum value of each row of $M$

$\displaystyle \max(M(i,:))=\begin{bmatrix} \max(m_{1,j}) \\ \max(m_{2,j}) \\ \vdots \\ \max(m_{100,j}) \end{bmatrix}$

and than we seek for the row in which there's the minimum of $\max(M(i,:))$ . It cames out to be $\boxed{1}$ .

Here's the MATLAB code for this algorithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

clear
M=zeros(100,100);
d=1;
%% map (input file)
map=[1 2;
2 3;
1 4;
1 5;
5 6;
3 7;
...and so on];   
%% Step 1.
   for i=1:size(map,1)
       M(map(i,1),map(i,2))=d;
       M(map(i,2),map(i,1))=d;
   end
   %% Step 2.
       while size(find(M==0),1)>100
            d=d+1;
   for h=1:100
       connectionI=find(M(h,:)==d-1);
       for k=1:size(connectionI,2)
          connectionII=find(M(connectionI(k),:)==1);
          for n=1:size(connectionII,2)
              if connectionII(n)~=h && (M(h,connectionII(n))==0 || M(h,connectionII(n))>d)
                  M(h,connectionII(n))=d;
                  M(connectionII(n),h)=d;
              end
          end
       end
   end
       end
       %% Final Result
       central=find(min(max(M)));