What is the the cost of combining categorical variables?
It depends on whether you retain the original columns or not.  You are not providing any additional information to the NN either way, so it's just a matter of how many features to compute in each batch.  That said, for the same reason, you might as well just use a value (e.g. -1 or 0) for the missing cities.  Depending on your implementation language, this is probably quicker easier to implement in terms of data engineering, and will amount to the same thing in terms of results.  Obviously the NN will need numerical values, so effectively you could just label encode the city feature and assign missing values to one of the labels.

There are some very minor considerations, such as if you combine state and city, you will end up with a larger label set for the single column, which, if you normalise to an appropriate range (e.g. 0 to 1), which NN's often benefit from and which can help to avoid exploding gradients, you will have a finer graduation than a column each for city and state.  Depending on the size and complexity of your data, this could have an impact on the NN's performance (prediction-wise) but it is likely to be a very minor effect compared to all of the other decisions you'll need to make in the process.