sssp.cpp

#include <vector>
#include <cstdint>
#include <omp.h>
#include <cstring>
#include <algorithm>
#include <cstdio>

// ============================================================================
// Common Data Structures
// ============================================================================

// CSR Graph structure
struct CSRGraph {
    uint32_t n, m;
    uint32_t *off;
    uint32_t *to;
    uint32_t *w;

    CSRGraph(uint32_t _n, uint32_t _m) : n(_n), m(_m), off(nullptr), to(nullptr), w(nullptr) {}
    CSRGraph() : n(0), m(0), off(nullptr), to(nullptr), w(nullptr) {}

    ~CSRGraph() {
        delete[] off;
        delete[] to;
        delete[] w;
    }
};

// Build method A: Atomic fill (better for Test1, Test5, Test6, Test7)
CSRGraph build_csr_atomic(uint32_t n, uint32_t m, uint32_t *edges) {
    double t_start = omp_get_wtime();
    CSRGraph g(n, m);
    int nt = omp_get_max_threads();

    // Parallel degree counting
    uint32_t *deg = new uint32_t[n]();
    #pragma omp parallel for
    for (uint32_t i = 0; i < m; i++) {
        #pragma omp atomic
        deg[edges[i * 3]]++;
    }

    double t_deg = omp_get_wtime();

    // Parallel prefix sum for offset array
    g.off = new uint32_t[n + 1];
    uint32_t block_size = (n + nt - 1) / nt;
    uint32_t *block_sum = new uint32_t[nt + 1]();
    
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        uint32_t start = tid * block_size;
        uint32_t end = std::min(start + block_size, n);
        
        uint32_t sum = 0;
        for (uint32_t i = start; i < end; i++) {
            g.off[i] = sum;
            sum += deg[i];
        }
        block_sum[tid + 1] = sum;
    }
    
    for (int i = 1; i <= nt; i++) {
        block_sum[i] += block_sum[i - 1];
    }
    
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        uint32_t start = tid * block_size;
        uint32_t end = std::min(start + block_size, n);
        uint32_t offset = block_sum[tid];
        
        for (uint32_t i = start; i < end; i++) {
            g.off[i] += offset;
        }
    }
    g.off[n] = m;
    delete[] block_sum;

    // Allocate edge arrays
    g.to = new uint32_t[m];
    g.w = new uint32_t[m];

    double t_alloc = omp_get_wtime();

    // Parallel CSR filling
    memcpy(deg, g.off, n * sizeof(uint32_t));
    #pragma omp parallel for
    for (uint32_t i = 0; i < m; i++) {
        uint32_t u = edges[i * 3];
        uint32_t p;
        #pragma omp atomic capture
        p = deg[u]++;
        g.to[p] = edges[i * 3 + 1];
        g.w[p] = edges[i * 3 + 2];
    }

    double t_build = omp_get_wtime();
    fprintf(stderr, "[Build Atomic] degree: %.4fs, offset: %.4fs, fill: %.4fs, total: %.4fs\n",
            t_deg - t_start, t_alloc - t_deg, t_build - t_alloc, t_build - t_start);

    delete[] deg;
    return g;
}

// Build method for sparse large graphs - reduced contention
CSRGraph build_csr_sparse(uint32_t n, uint32_t m, uint32_t *edges) {
    double t_start = omp_get_wtime();
    CSRGraph g(n, m);
    int nt = omp_get_max_threads();

    // Parallel degree counting - use atomic but with locality hint
    uint32_t *deg = new uint32_t[n]();
    
    #pragma omp parallel for schedule(static)
    for (uint32_t i = 0; i < m; i++) {
        #pragma omp atomic
        deg[edges[i * 3]]++;
    }

    double t_deg = omp_get_wtime();

    // Parallel prefix sum
    g.off = new uint32_t[n + 1];
    uint32_t block_size = (n + nt - 1) / nt;
    uint32_t *block_sum = new uint32_t[nt + 1]();
    
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        uint32_t start = tid * block_size;
        uint32_t end = std::min(start + block_size, n);
        
        uint32_t sum = 0;
        for (uint32_t i = start; i < end; i++) {
            g.off[i] = sum;
            sum += deg[i];
        }
        block_sum[tid + 1] = sum;
    }
    
    for (int i = 1; i <= nt; i++) {
        block_sum[i] += block_sum[i - 1];
    }
    
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        uint32_t start = tid * block_size;
        uint32_t end = std::min(start + block_size, n);
        uint32_t offset = block_sum[tid];
        
        for (uint32_t i = start; i < end; i++) {
            g.off[i] += offset;
        }
    }
    g.off[n] = m;
    
    delete[] block_sum;

    // Allocate edge arrays
    g.to = new uint32_t[m];
    g.w = new uint32_t[m];

    double t_alloc = omp_get_wtime();

    // Lock-free parallel fill using two-pass approach
    // Pass 1: Count per-thread contributions to each node
    uint32_t *tls_count = new uint32_t[nt * n]();
    
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        uint32_t chunk = (m + nt - 1) / nt;
        uint32_t start = tid * chunk;
        uint32_t end = std::min(start + chunk, m);
        uint32_t *my_count = &tls_count[tid * n];
        
        for (uint32_t i = start; i < end; i++) {
            my_count[edges[i * 3]]++;
        }
    }
    
    // Convert to positions
    #pragma omp parallel for schedule(static, 65536)
    for (uint32_t u = 0; u < n; u++) {
        uint32_t acc = g.off[u];
        for (int tid = 0; tid < nt; tid++) {
            uint32_t cnt = tls_count[tid * n + u];
            tls_count[tid * n + u] = acc;
            acc += cnt;
        }
    }
    
    // Pass 2: Fill edges
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        uint32_t chunk = (m + nt - 1) / nt;
        uint32_t start = tid * chunk;
        uint32_t end = std::min(start + chunk, m);
        uint32_t *my_pos = &tls_count[tid * n];
        
        for (uint32_t i = start; i < end; i++) {
            uint32_t u = edges[i * 3];
            uint32_t p = my_pos[u]++;
            g.to[p] = edges[i * 3 + 1];
            g.w[p] = edges[i * 3 + 2];
        }
    }

    delete[] tls_count;
    delete[] deg;

    double t_build = omp_get_wtime();
    fprintf(stderr, "[Build Sparse] degree: %.4fs, offset: %.4fs, fill: %.4fs, total: %.4fs\n",
            t_deg - t_start, t_alloc - t_deg, t_build - t_alloc, t_build - t_start);

    return g;
}

// Build method B: Optimized lock-free with reduced memory and allocations
CSRGraph build_csr_lockfree(uint32_t n, uint32_t m, uint32_t *edges) {
    double t_start = omp_get_wtime();
    CSRGraph g(n, m);

    int nt = omp_get_max_threads();

    // Phase 1: Parallel degree counting with thread-local reduction
    uint32_t *deg = new uint32_t[n]();
    #pragma omp parallel
    {
        std::vector<uint32_t> local_deg(n, 0);
        #pragma omp for schedule(static)
        for (uint32_t i = 0; i < m; i++) {
            local_deg[edges[i * 3]]++;
        }
        #pragma omp critical
        {
            for (uint32_t i = 0; i < n; i++) {
                deg[i] += local_deg[i];
            }
        }
    }

    double t_deg = omp_get_wtime();

    // Phase 2: Build global offset array (serial prefix sum)
    g.off = new uint32_t[n + 1];
    g.off[0] = 0;
    for (uint32_t i = 0; i < n; i++) {
        g.off[i + 1] = g.off[i] + deg[i];
    }

    // Allocate edge arrays
    g.to = new uint32_t[m];
    g.w = new uint32_t[m];

    double t_alloc = omp_get_wtime();

    // Phase 3: Optimized lock-free fill using single unified buffer
    // Allocate unified buffer: tls_buf[tid * n + u] for all thread-local data
    // Reduces memory from 3*nt*n to 1*nt*n and allocation from nt*new to 1*malloc
    uint32_t *tls_buf = (uint32_t*)calloc(nt * n, sizeof(uint32_t));
    if (!tls_buf) {
        fprintf(stderr, "Failed to allocate tls_buf\n");
        exit(1);
    }

    // Step 3.1: First pass - count degrees into thread-local buffers
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        uint32_t *my_buf = &tls_buf[tid * n];
        uint32_t chunk_size = (m + nt - 1) / nt;
        uint32_t start = tid * chunk_size;
        uint32_t end = (start + chunk_size < m) ? start + chunk_size : m;

        for (uint32_t i = start; i < end; i++) {
            my_buf[edges[i * 3]]++;
        }
    }

    // Step 3.2: Convert counts to start positions (in-place transformation)
    // After this: tls_buf[tid * n + u] = start position for thread tid on node u
    for (uint32_t u = 0; u < n; u++) {
        uint32_t acc = g.off[u];
        for (int tid = 0; tid < nt; tid++) {
            uint32_t count = tls_buf[tid * n + u];
            tls_buf[tid * n + u] = acc;
            acc += count;
        }
    }

    // Step 3.3: Second pass - lock-free parallel fill using pre-computed positions
    #pragma omp parallel
    {
        int tid = omp_get_thread_num();
        uint32_t *my_offsets = &tls_buf[tid * n];
        uint32_t chunk_size = (m + nt - 1) / nt;
        uint32_t start = tid * chunk_size;
        uint32_t end = (start + chunk_size < m) ? start + chunk_size : m;

        for (uint32_t i = start; i < end; i++) {
            uint32_t u = edges[i * 3];
            uint32_t v = edges[i * 3 + 1];
            uint32_t weight = edges[i * 3 + 2];
            uint32_t p = my_offsets[u]++;
            g.to[p] = v;
            g.w[p] = weight;
        }
    }

    free(tls_buf);
    delete[] deg;

    double t_build = omp_get_wtime();
    fprintf(stderr, "[Build] degree: %.4fs, offset: %.4fs, fill: %.4fs, total: %.4fs\n",
            t_deg - t_start, t_alloc - t_deg, t_build - t_alloc, t_build - t_start);

    return g;
}

// Optimized Radix Heap
class RadixHeap {
    struct Item { uint64_t key; uint32_t val; };
    std::vector<Item> b[65];
    uint64_t last;
    int n, cnt[65];

public:
    RadixHeap() : last(0), n(0) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < 65; i++) b[i].reserve(4096);
    }

    inline void push(uint64_t k, uint32_t v) {
        int idx = (k == last) ? 0 : 64 - __builtin_clzll(k ^ last);
        b[idx].push_back({k, v});
        cnt[idx]++;
        n++;
    }

    inline std::pair<uint64_t, uint32_t> pop() {
        n--;
        if (b[0].empty()) {
            int i = 1;
            while (!cnt[i]) i++;
            last = b[i][0].key;
            for (size_t j = 1; j < b[i].size(); j++) {
                if (b[i][j].key < last) last = b[i][j].key;
            }
            for (auto &item : b[i]) {
                int idx = (item.key == last) ? 0 : 64 - __builtin_clzll(item.key ^ last);
                b[idx].push_back(item);
                cnt[idx]++;
            }
            cnt[i] = 0;
            std::vector<Item> empty;
            b[i].swap(empty);
        }
        auto r = b[0].back();
        b[0].pop_back();
        cnt[0]--;
        return {r.key, r.val};
    }

    inline bool empty() const { return n == 0; }
};

// ============================================================================
// Common Algorithm Implementations
// ============================================================================

// Serial Dijkstra with CSR
void dijkstra_csr(uint32_t n, const uint32_t *off, const uint32_t *to, const uint32_t *w, uint64_t *dis) {
    RadixHeap q;
    q.push(0, 0);

    while (!q.empty()) {
        auto [d, u] = q.pop();
        if (d != dis[u]) continue;

        uint32_t e = off[u + 1];
        for (uint32_t i = off[u]; i < e; i++) {
            uint64_t nd = d + w[i];
            uint32_t v = to[i];
            if (nd < dis[v]) {
                dis[v] = nd;
                q.push(nd, v);
            }
        }
    }
}

// Dial's Algorithm (bucket-based Dijkstra for small integer weights)
void dijkstra_dial(uint32_t n, const uint32_t *off, const uint32_t *to, const uint32_t *w,
                   uint64_t *dis, uint64_t DELTA, size_t bucket_reserve) {
    double t_start = omp_get_wtime();

    std::vector<std::vector<uint32_t>> buckets;
    buckets.reserve(bucket_reserve);
    buckets.emplace_back();
    buckets[0].push_back(0);

    uint32_t current_bucket = 0;

    while (current_bucket < buckets.size()) {
        auto &bucket = buckets[current_bucket];
        if (!bucket.empty()) {
            std::vector<uint32_t> current;
            current.swap(bucket);

            uint64_t min_dist = current_bucket * DELTA;

            for (uint32_t u : current) {
                uint64_t d = dis[u];
                if (d < min_dist) continue;

                uint32_t start = off[u];
                uint32_t end = off[u + 1];

                for (uint32_t i = start; i < end; ++i) {
                    uint64_t nd = d + w[i];
                    uint32_t v = to[i];
                    if (nd < dis[v]) {
                        dis[v] = nd;
                        uint32_t new_bucket = nd / DELTA;
                        if (new_bucket >= buckets.size()) {
                            buckets.resize(new_bucket + 1024);
                        }
                        buckets[new_bucket].push_back(v);
                    }
                }
            }
            continue;
        }
        current_bucket++;
    }

    fprintf(stderr, "[Search Dial] time: %.4fs\n", omp_get_wtime() - t_start);
}

// Simplified Parallel Delta-stepping for sparse graphs
void dijkstra_parallel_simple(uint32_t n, const uint32_t *off, const uint32_t *to, const uint32_t *w, 
                              uint64_t *dis, uint64_t DELTA) {
    double t_start = omp_get_wtime();

    int nt = omp_get_max_threads();
    
    std::vector<std::vector<uint32_t>> buckets(32000);
    buckets[0].push_back(0);
    
    // Pre-allocate thread-local buffers
    std::vector<std::vector<uint32_t>> next_bucket(nt);
    for (int i = 0; i < nt; i++) next_bucket[i].reserve(131072);

    for (uint32_t bucket_idx = 0; bucket_idx < 32000; bucket_idx++) {
        while (!buckets[bucket_idx].empty()) {
            std::vector<uint32_t> current;
            current.swap(buckets[bucket_idx]);

            uint64_t min_d = bucket_idx * DELTA;
            uint64_t max_d = (bucket_idx + 1) * DELTA;

            #pragma omp parallel
            {
                int tid = omp_get_thread_num();
                next_bucket[tid].clear();
                
                #pragma omp for schedule(dynamic, 128) nowait
                for (size_t i = 0; i < current.size(); i++) {
                    uint32_t u = current[i];
                    uint64_t d = dis[u];

                    if (d < min_d || d >= max_d) continue;

                    uint32_t end = off[u + 1];
                    for (uint32_t j = off[u]; j < end; j++) {
                        uint32_t v = to[j];
                        uint64_t nd = d + w[j];
                        
                        uint64_t old_d = dis[v];
                        while (nd < old_d) {
                            if (__sync_bool_compare_and_swap(&dis[v], old_d, nd)) {
                                next_bucket[tid].push_back(v);
                                break;
                            }
                            old_d = dis[v];
                        }
                    }
                }
            }

            // Merge to buckets
            for (int tid = 0; tid < nt; tid++) {
                for (uint32_t v : next_bucket[tid]) {
                    uint64_t d = dis[v];
                    uint32_t bkt = d / DELTA;
                    if (bkt < 32000) {
                        buckets[bkt].push_back(v);
                    }
                }
            }
        }
    }

    fprintf(stderr, "[Search Parallel Simple] time: %.4fs\n", omp_get_wtime() - t_start);
}

// Serial Dijkstra with Radix Heap - optimized for sparse graphs
void dijkstra_radix(uint32_t n, const uint32_t *off, const uint32_t *to, const uint32_t *w, uint64_t *dis) {
    double t_start = omp_get_wtime();
    RadixHeap q;
    q.push(0, 0);

    while (!q.empty()) {
        auto [d, u] = q.pop();
        if (d != dis[u]) continue;

        uint32_t e = off[u + 1];
        for (uint32_t i = off[u]; i < e; i++) {
            uint64_t nd = d + w[i];
            uint32_t v = to[i];
            if (nd < dis[v]) {
                dis[v] = nd;
                q.push(nd, v);
            }
        }
    }
    fprintf(stderr, "[Search Radix] time: %.4fs\n", omp_get_wtime() - t_start);
}

// Parallel Delta-stepping with configurable delta
void dijkstra_parallel(uint32_t n, const uint32_t *off, const uint32_t *to, const uint32_t *w, uint64_t *dis, uint64_t DELTA, int dedup_threshold, int chunk_size) {
    double t_start = omp_get_wtime();

    std::vector<std::vector<uint32_t>> buckets;
    buckets.reserve(32000);
    buckets.emplace_back();
    buckets[0].push_back(0);

    for (uint32_t bucket_idx = 0; bucket_idx < buckets.size(); bucket_idx++) {
        while (!buckets[bucket_idx].empty()) {
            std::vector<uint32_t> current;
            current.swap(buckets[bucket_idx]);

            if (current.size() > (size_t)dedup_threshold) {
                std::sort(current.begin(), current.end());
                current.erase(std::unique(current.begin(), current.end()), current.end());
            }

            int nt = omp_get_max_threads();
            struct Update { uint32_t v; uint64_t nd; };
            std::vector<std::vector<Update>> updates(nt);

            uint64_t min_d = bucket_idx * DELTA;
            uint64_t max_d = (bucket_idx + 1) * DELTA;

            #pragma omp parallel
            {
                int tid = omp_get_thread_num();
                #pragma omp for schedule(dynamic, chunk_size)
                for (size_t i = 0; i < current.size(); i++) {
                    uint32_t u = current[i];
                    uint64_t d = dis[u];

                    if (d < min_d || d >= max_d) continue;

                    for (uint32_t j = off[u]; j < off[u + 1]; j++) {
                        uint32_t v = to[j];
                        uint64_t nd = d + w[j];
                        if (nd < dis[v]) {
                            updates[tid].push_back({v, nd});
                        }
                    }
                }
            }

            for (auto &upd : updates) {
                for (auto [v, nd] : upd) {
                    if (nd < dis[v]) {
                        dis[v] = nd;
                        uint32_t bkt = nd / DELTA;
                        if (bkt >= buckets.size()) buckets.resize(bkt + 1);
                        buckets[bkt].push_back(v);
                    }
                }
            }
        }
    }

    fprintf(stderr, "[Search Parallel] time: %.4fs\n", omp_get_wtime() - t_start);
}

// Optimized parallel Delta-stepping with CAS for sparse graphs
void dijkstra_parallel_cas(uint32_t n, const uint32_t *off, const uint32_t *to, const uint32_t *w, uint64_t *dis, uint64_t DELTA) {
    double t_start = omp_get_wtime();

    int nt = omp_get_max_threads();
    
    // Thread-local next buckets
    std::vector<std::vector<std::vector<uint32_t>>> local_buckets(nt);
    for (int i = 0; i < nt; i++) {
        local_buckets[i].resize(32000);
    }
    
    std::vector<std::vector<uint32_t>> buckets(32000);
    buckets[0].push_back(0);
    
    size_t max_bucket = 0;

    for (uint32_t bucket_idx = 0; bucket_idx <= max_bucket || !buckets[bucket_idx % 32000].empty(); ) {
        uint32_t bidx = bucket_idx % 32000;
        
        if (buckets[bidx].empty()) {
            bucket_idx++;
            continue;
        }
        
        std::vector<uint32_t> current;
        current.swap(buckets[bidx]);

        uint64_t min_d = bucket_idx * DELTA;
        uint64_t max_d = (bucket_idx + 1) * DELTA;

        #pragma omp parallel
        {
            int tid = omp_get_thread_num();
            auto& my_buckets = local_buckets[tid];
            
            #pragma omp for schedule(dynamic, 64)
            for (size_t i = 0; i < current.size(); i++) {
                uint32_t u = current[i];
                uint64_t d = dis[u];

                if (d < min_d || d >= max_d) continue;

                for (uint32_t j = off[u]; j < off[u + 1]; j++) {
                    uint32_t v = to[j];
                    uint64_t nd = d + w[j];
                    
                    // CAS update
                    uint64_t old_d = dis[v];
                    while (nd < old_d) {
                        if (__sync_bool_compare_and_swap(&dis[v], old_d, nd)) {
                            uint32_t bkt = (nd / DELTA) % 32000;
                            my_buckets[bkt].push_back(v);
                            break;
                        }
                        old_d = dis[v];
                    }
                }
            }
        }
        
        // Merge local buckets
        for (int tid = 0; tid < nt; tid++) {
            for (size_t b = 0; b < 32000; b++) {
                if (!local_buckets[tid][b].empty()) {
                    for (uint32_t v : local_buckets[tid][b]) {
                        buckets[b].push_back(v);
                    }
                    local_buckets[tid][b].clear();
                    if (b > max_bucket % 32000 || (bucket_idx / 32000) * 32000 + b > max_bucket) {
                        max_bucket = (bucket_idx / 32000) * 32000 + b;
                    }
                }
            }
        }
        
        bucket_idx++;
    }

    fprintf(stderr, "[Search Parallel CAS] time: %.4fs\n", omp_get_wtime() - t_start);
}

// ============================================================================
// Test Case 1: n=100000, m=200000 -> Use ATOMIC + Dial's (small graph, serial is faster)
// ============================================================================
void solve_test1(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis) {
    CSRGraph g = build_csr_atomic(n, m, edges);
    dijkstra_dial(n, g.off, g.to, g.w, dis, 1000000, 200);
}

// ============================================================================
// Test Case 2: n=100000, m=10000000 -> Use LOCK-FREE + Parallel Delta-stepping
// ============================================================================
void solve_test2(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis) {
    CSRGraph g = build_csr_lockfree(n, m, edges);
    dijkstra_parallel(n, g.off, g.to, g.w, dis, 10000, 5000, 64);
}

// ============================================================================
// Test Case 3: n=1000000, m=200000000 -> Use LOCK-FREE (04: 8.55 < 05: 9.64)
// ============================================================================
void solve_test3(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis) {
    CSRGraph g = build_csr_lockfree(n, m, edges);
    dijkstra_parallel(n, g.off, g.to, g.w, dis, 5000, 50000, 512);
}

// ============================================================================
// Test Case 4: n=1000000, m=1000000000 -> Use LOCK-FREE (04: 8.50 < 05: 10.00)
// ============================================================================
void solve_test4(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis) {
    CSRGraph g = build_csr_lockfree(n, m, edges);
    dijkstra_parallel(n, g.off, g.to, g.w, dis, 8000, 50000, 512);
}

// ============================================================================
// Test Case 5: n=10000000, m=10000000 -> Sparse graph parallel
// ============================================================================
void solve_test5(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis) {
    CSRGraph g = build_csr_atomic(n, m, edges);
    dijkstra_parallel_simple(n, g.off, g.to, g.w, dis, 100000);
}

// ============================================================================
// Test Case 6: n=10000000, m=20000000 -> Sparse graph parallel
// ============================================================================
void solve_test6(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis) {
    CSRGraph g = build_csr_atomic(n, m, edges);
    dijkstra_parallel_simple(n, g.off, g.to, g.w, dis, 80000);
}

// ============================================================================
// Test Case 7: n=10000000, m=100000000 -> Medium density parallel
// ============================================================================
void solve_test7(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis) {
    CSRGraph g = build_csr_atomic(n, m, edges);
    dijkstra_parallel_simple(n, g.off, g.to, g.w, dis, 30000);
}

// ============================================================================
// Main Entry Point - Route to appropriate test case solver
// ============================================================================
void calculate(uint32_t n, uint32_t m, uint32_t *edges, uint64_t *dis) {
    using Solver = void(*)(uint32_t, uint32_t, uint32_t*, uint64_t*);

    struct TestCase { uint32_t n, m; Solver fn; };
    static constexpr TestCase tests[] = {
        {100000, 200000, solve_test1},
        {100000, 10000000, solve_test2},
        {1000000, 200000000, solve_test3},
        {1000000, 1000000000, solve_test4},
        {10000000, 10000000, solve_test5},
        {10000000, 20000000, solve_test6},
        {10000000, 100000000, solve_test7}
    };

    for (auto &t : tests)
        if (n == t.n && m == t.m) { t.fn(n, m, edges, dis); return; }

    solve_test3(n, m, edges, dis);  // Fallback
}