Calculating Euclidean distance
I see a few things that may help you improve your code.  

Sort the input

If the input is sorted, we can assure that the City id for vectors is strictly non-decreasing.  I'd add these two things for that.

std::sort(input.begin(), input.end());


And then this member function:

bool City::operator&lt;(const City &amp;other) const { 
    return id &lt; other.id; 
}


Don't repeat calculations

Unless there's something very strange, the distance from city A to city B is the same as the distance from city B to city A.  For that reason, we can populate the vectors two at a time:

for (int c1 = 0; c1 &lt; input.size(); c1++) {
    for (int c2 = c1; c2 &lt; input.size(); c2++) {
        input[c1].addNeighbor(input[c2]);
        input[c2].addNeighbor(input[c1]);
    }
} 


This is also why I suggested to sort the input vector.  I would also suggest calculating the distance once and then using it for both vector additions.  Doing that will require a little more code restructuring.  The inner loop can simply be this:

input[c1].addNeighbor(input[c2]);


And rewrite the member function like this:

void City::addNeighbor(City &amp;city) {
    if (getCityID() == city.getCityID()) {
        return;
    }
    unsigned distance = Utilities::distanceSquared(*this, city);
    neighbors.emplace_back(Neighbor{city.getCityID(), distance});
    city.neighbors.emplace_back(Neighbor{getCityID(), distance});
}


Note that we avoid calculating the distance if they are the same ID, but not if the distance between them is actually zero.  In this case the argument to the function must not be const because we need also to modify it.  

Also, although you did not provide the code for it, I notice that you have a NearestNeighbor() function.  There are some efficient ways to deal with that, depending on how you intend to use it.  One could sort the vectors (once) when population of them is complete or one might use a std::priority_queue instead of a std::vector.

Pass const references where practical

Passing an object by value can cause an object copy.  For example this function:

unsigned int Utilities::distanceSquared(City a, City b);


should instead be written like this:

unsigned int Utilities::distanceSquared(const City &amp;a, const City &amp;b);


Avoid floating point if only integers are needed

Integer operations are usually faster than floating point operations.  So here's how I'd write your distanceSquared function:

namespace Utilities {
unsigned int distanceSquared(const City &amp;a, const City &amp;b) {
    int dx{b.getXCoord() - a.getXCoord()};
    int dy{b.getYCoord() - a.getYCoord()};
    return dx*dx + dy*dy;
}
}


As @TobySpeight correctly points out, this assumes that no overflow occurs.  On my randomly generated test data, the ranges of the x and y coordinates are restricted so that is guaranteed, with my compiler, that no overflow can occur, but it's worth verifying that for your real data as well.