代码

#include "router.h"
#include <arpa/inet.h>
struct RoutingTableNode {
    RoutingTableNode *nx[2];
    bool hasRoute;
    unsigned int nexthop;
    RoutingTableNode() {
        nx[0] = nx[1] = nullptr;
        hasRoute = false;
    }
} *root = nullptr;
void init(int n, int q, const RoutingTableEntry *a) {
    root = new RoutingTableNode();
    for (int i = 0; i < n; i++) {
        RoutingTableNode *now = root;
        unsigned int addr = htonl(a[i].addr);
        for (int i = 0; i < a[i].len; i++) {
            int nw = (addr & 0x80000000) != 0 ;
            addr <<= 1;
            if (!now->nx[nw]) {
                now->nx[nw] = new RoutingTableNode();
            }
            now = now->nx[nw];
        }
        now->hasRoute = true;
        now->nexthop = a[i].nexthop;
    }
}

unsigned query(unsigned addr) {
    RoutingTableNode *now = root;
    addr = htonl(addr);
    RoutingTableNode *found = nullptr;
    if (now->hasRoute) {
        found = now;
    }
    for (int i = 0; i < 32; i++) {
        int nw = (addr & 0x80000000) != 0;
        addr <<= 1;
        if (!now->nx[nw]) {
            break;
        }
        now = now->nx[nw];
        if (now->hasRoute) {
            found = now;
        }
    }
    if (!found) {
        return 0;
    }
    return found->nexthop;
}

评测结果