In Haskell, these direct equivalents aren’t bad at all:

    cityToState = Map.fromList
      [ (city, state)
      | (state, cities) <- Map.toList citiesByState
      , city <- cities
      ]

    cityToState = Map.fromList $ do
      (state, cities) <- Map.toList citiesByState
      city <- cities
      pure (city, state)

For multiple “nested loops”, I generally prefer do-notation over both list comprehensions and combinators such as concatMap, unless the structure is simple enough that the combinator version is much shorter.