Combined category search with two Dropdown Menus

I was thinking of “abusing” 😉 WordPress to do some sort of CMS work. Basically think of a simple restaurant catalogue. Each post is a review of a restaurant I have been to.

Restaurants are categorized as “chinese, italian, greek, irish pub, vegan, vegetarian”

And then there is a main-category “cities” with lots of subcategories London, Paris, Berlin, Milano, Rome, Venice, Barcelona.

So far no big deal. Really not.

On the main page I want to have two dropdown Menu’s

choose your taste (“chinese, italian…”)…
choose your city (“london, paris, … )…

And a submit button… and then its gonna do a combined category search, listing all restaurants found in “chinese” and in “Berlin”…

How do I do that?