Here's my solution:
The first thing we notice is that
This problem will be a lot simpler if we use complementary counting to find the answer.
Using this idea, we see that there are
two possibilities that make it impossible to go from one city to another. The first one is if all roads connected to that city point away from that city. Then, there is literally no way to get to that city. Another possibility is that all roads connected to that city point towards that city. Then, there is no way to start from that city and get to any other city.
We now calculate the number of ways for this to happen:
There are $5$ cities and $10$ roads, and we are setting the direction of $4$ of these roads, so there are $2^{10-4}\cdot 5 = 320$ ways to do the first case. The second case is similar in idea and also has $320$ ways to do this.
But, we see that:
There is overcounting. For example, we could have city A having all roads pointing towards it and city B all roads pointing away from it. The number of overcounted cases is $5\cdot 4 = 20$ ways to choose the two cities, and $2^3$ ways to rearrange the roads that are not defined by the two cities.
Hence, the total is
$320 + 320 - 160 = 480$.
But, we have to
Subtract that from the total because we used complementary counting so the answer is now $2^{10} - 480 = \boxed{544}$ and we are done.
This problem comes from here:
This problem...don't click here if you don't want the answer.