First we make a construction for odd $n$, and obviously interpret this in graph theoretic language as a directed graph (although unnecessary ) Denote as $d(G)$ as the sum of all $d(A, B)$ in graph $G$ First, arrange the vertices in a circle and orient the edges clockwise. Next, starting from every vertex, orient the edges to rest of the polygon alternating, we are able to do this because we picked odd $n$. Now obviously from any vertex $A$ to half of the other vertices is a path of length $1$ and half of the path are length $2$. Simple calculation gives $d(G) = 3$$ {n}\choose{2}$. Now consider $n$ even. Make the construction for $n-1$ and add a new vertex : make two of it's edges point in two consecutive vertices on the $n-1$ polygon, and the rest pointing to the new vertex. The two of the consecutive vertices will point to the rest of the $n-1$ polygon, so every vertex will have a path of length at most $2$ to the new one and vice versa. Note that this does not hold for $n=4$, because it is two small and one of the vertices will not have a path to the new one. The case $n=4$ doesn't work and is proven separately to have a bigger average. To prove this is optimal, consider any pair of vertices : there will be path from one to the other of length $1$ and the other path is at least $2$, so the total sum will be at least $3$$ {n}\choose{2}$, so we are done. The average is then this divided by number of unordered pairs of vertices, so it is $3/2$ $\blacksquare$ I hope the solution is correct, and can someone please tell me what is CHKMO NOTE: The former solution was wrong, as pointed out by gfyerin

niksic wrote: I hope the solution is correct, and can someone please tell me what is CHKMO It is the (China) Hong Kong Math Olympiad.

I think the official name is Hong Kong National Olympiad.

i think an average of $1.5$ can be achieved in even $N$ too. Let $M=\frac{N}{2}$, lets split the cities into two halves $1,2,3,...,M$ and $M+1,M+2,...,N$. Then, for each pair of $1 \le i,j, \le M$, add edge $i \rightarrow M+j$ if $i \neq j$ and $M+j \rightarrow i$ otherwise. Then, add edge $i \rightarrow j$ iff $i < j$. Then, add edge $M+j \rightarrow M+i$ iff $i < j$ . But then. switch the direction of edge $1 \rightarrow M$ and $N \rightarrow M+1$. I think this construction should work for all even $N$ that is not $4$.

For $N=4$, it is easy to notice that all strongly connected components of size 4 are isomorphic and you can just check that single one without any casework.