Nie znam C++, więc nie napiszę kodu, ale do głowy przychodzi mi takie rozwiązanie:
1. Pobierasz od użytkownika liczbę miast - n.
2. Tworzysz tablicę n-elementową i dla każdego jej elementu generujesz losową liczbę z zakresu [-100 000; 100 000].
3. "Przelatujesz" n razy całą tablicę sumując elementy od 1 do n, 1 do n-1 ... 1 do 2, potem 2 do n, 2 do n-1 itd. aż do n-1 do n.
4. Wyniki możesz zapisywać do innej tablicy i potem wybrać największy, albo wprowadzić do pętli jakąś zmienną np. max.