Here is some code that should do the trick:

//Creates special permastruct that turns all terms of cities into slugs
add_action( 'init', 'set_rewrite' );

function set_rewrite() {
    //Get terms
    $terms = get_terms( 'cities', array( 'hide_empty' => false ) );
    //return if no terms
    if( count( $terms ) < 1 ) return;
    $slugs = wp_list_pluck( $terms, 'slug' );
    //create term regex
    $termregex = '(' . implode( '|', $slugs) . ')';
    //New query var
    add_rewrite_tag( '%cityname%', $termregex );
    //Add permastruct
    add_permastruct( 'cities_struct', '%cityname%/' );
}

//action to refresh rewrite rules when a new term is saved
add_action( 'created_cities', 'refresh_cities' );
add_action( 'edited_cities', 'refresh_cities' );
add_action( 'delete_cities', 'refresh_cities' );


function refresh_cities() {
    global $wp_rewrite;
    $wp_rewrite -> flush_rules();
}

//set city name to the taxonomy cities
add_filter( 'parse_query', 'parse_cities_query' );

function parse_cities_query( $query ) {
    if( !empty( $query->query_vars['cityname'] ) ) $query->set( 'cities', $query->query_vars['cityname'] )
}   

Basically this creates a special permastruct that uses the slugs of the taxonomy cities as its base. It creates a query variable called cityname, which only accepts the slugs of the taxonomy and then sends the result to the proper taxonomy query variable.

Here is some code that should do the trick:

//Creates special permastruct that turns all terms of cities into slugs
add_action( 'init', 'set_rewrite' );

function set_rewrite() {
    //Get terms
    $terms = get_terms( 'cities', array( 'hide_empty' => false ) );
    //return if no terms
    if( count( $terms ) < 1 ) return;
    $slugs = wp_list_pluck( $terms, 'slug' );
    //create term regex
    $termregex = '(' . implode( '|', $slugs) . ')';
    //New query var
    add_rewrite_tag( '%cityname%', $termregex );
    //Add permastruct
    add_permastruct( 'cities_struct', '%cityname%/' );
    //refresh if new term added
    if( get_option( 'update_cities_struct' ) ) {
        global $wp_rewrite;
        $wp_rewrite -> flush_rules();
        update_option( 'update_cities_struct', 0 );
    }
}

//action to refresh rewrite rules when a new term is saved
add_action( 'created_cities', 'refresh_cities' );
add_action( 'edited_cities', 'refresh_cities' );
add_action( 'delete_cities', 'refresh_cities' );


function refresh_cities() {
    update_option( 'update_cities_struct', 1 );
}

//set city name to the taxonomy cities
add_filter( 'parse_query', 'parse_cities_query' );

function parse_cities_query( $query ) {
    if( !empty( $query->query_vars['cityname'] ) ) $query->set( 'cities', $query->query_vars['cityname'] )
}   

Basically this creates a special permastruct that uses the slugs of the taxonomy cities as its base. It creates a query variable called cityname, which only accepts the slugs of the taxonomy and then sends the result to the proper taxonomy query variable.