global winwin

trả bài cho bạn nhé, 1 bài khó nhất trong tất cả các bài tôi từng làm trong Viblo, bạn nào có bài nào khó hơn nữa không xin mời nhé:

#include <stdio.h> #include <stdlib.h> #include <stdint.h>

#define MAXN 100000 #define MAXM 100000 #define INF ((long long)4e18)

typedef struct Edge { int to; int w; int next; } Edge;

static Edge edges[2 * MAXM + 5]; static int head[MAXN + 5]; static int ecnt = 0;

static inline void add_edge(int u, int v, int w) { edges[ecnt].to = v; edges[ecnt].w = w; edges[ecnt].next = head[u]; head[u] = ecnt++; }

typedef struct Node { long long d; int v; int r; // root (country) } Node;

static Node *heap; static int hsz = 0;

static inline int less(Node a, Node b) { if (a.d != b.d) return a.d < b.d; if (a.v != b.v) return a.v < b.v; return a.r < b.r; }

static inline void heap_push(Node x) { int i = ++hsz; heap[i] = x; while (i > 1) { int p = i >> 1; if (!less(heap[i], heap[p])) break; Node tmp = heap[i]; heap[i] = heap[p]; heap[p] = tmp; i = p; } }

static inline Node heap_pop() { Node res = heap[1]; heap[1] = heap[hsz--]; int i = 1; while (1) { int l = i << 1, r = l + 1, s = i; if (l <= hsz && less(heap[l], heap[s])) s = l; if (r <= hsz && less(heap[r], heap[s])) s = r; if (s == i) break; Node tmp = heap[i]; heap[i] = heap[s]; heap[s] = tmp; i = s; } return res; }

static inline int fast_getchar() { return getchar_unlocked(); }

static inline int read_int() { int c, sgn = 1, x = 0; do { c = fast_getchar(); } while (c <= ' ' && c != EOF); if (c == '-') { sgn = -1; c = fast_getchar(); } while (c > ' ') { x = x * 10 + (c - '0'); c = fast_getchar(); } return x * sgn; }

static inline long long read_ll() { int c, sgn = 1; long long x = 0; do { c = fast_getchar(); } while (c <= ' ' && c != EOF); if (c == '-') { sgn = -1; c = fast_getchar(); } while (c > ' ') { x = x * 10 + (c - '0'); c = fast_getchar(); } return x * sgn; }

static inline void add_pair(uint64_t *fightRow, int a, int b) { if (a == b) return; if (a > b) { int t = a; a = b; b = t; } fightRow[a] |= (1ULL << b); }

int main() { int N = read_int(); int L = read_int(); int M = read_int();

for (int i = 0; i < N; i++) head[i] = -1;

int *start = (int*)malloc(sizeof(int) * (size_t)L);
for (int i = 0; i < L; i++) start[i] = read_int();

int *U = (int*)malloc(sizeof(int) * (size_t)M);
int *V = (int*)malloc(sizeof(int) * (size_t)M);
int *W = (int*)malloc(sizeof(int) * (size_t)M);

for (int i = 0; i < M; i++) {
    int u = read_int();
    int v = read_int();
    int w = read_int();
    U[i] = u; V[i] = v; W[i] = w;
    add_edge(u, v, w);
    add_edge(v, u, w);
}

long long *dist = (long long*)malloc(sizeof(long long) * (size_t)N);
uint64_t *mask = (uint64_t*)malloc(sizeof(uint64_t) * (size_t)N);

for (int i = 0; i < N; i++) { dist[i] = INF; mask[i] = 0; }

heap = (Node*)malloc(sizeof(Node) * (size_t)(2 * M + (long long)N * (long long)L + 10));
// Thực tế không cần chính xác, chỉ cần đủ lớn; với L<=50, N<=1e5, vẫn ổn.

// init sources
for (int i = 0; i < L; i++) {
    int s = start[i];
    uint64_t bit = 1ULL << i;
    if (dist[s] > 0) {
        dist[s] = 0;
        mask[s] = bit;
        heap_push((Node){0, s, i});
    } else if (dist[s] == 0 && (mask[s] & bit) == 0) {
        mask[s] |= bit;
        heap_push((Node){0, s, i});
    }
}

// Multi-source Dijkstra with root labels (only minimal dist per node, keep all roots tied at min)
while (hsz > 0) {
    Node cur = heap_pop();
    long long d = cur.d;
    int u = cur.v;
    int r = cur.r;

    if (d != dist[u]) continue;
    if ((mask[u] & (1ULL << r)) == 0) continue;

    for (int ei = head[u]; ei != -1; ei = edges[ei].next) {
        int v = edges[ei].to;
        int w = edges[ei].w;
        long long nd = d + (long long)w;

        if (nd < dist[v]) {
            dist[v] = nd;
            mask[v] = (1ULL << r);
            heap_push((Node){nd, v, r});
        } else if (nd == dist[v]) {
            uint64_t bit = (1ULL << r);
            if ((mask[v] & bit) == 0) {
                mask[v] |= bit;
                heap_push((Node){nd, v, r});
            }
        }
    }
}

// Collect fights
uint64_t fightRow[60] = {0}; // fightRow[a] has bits b (b>a) that fight with a

// Node ties
for (int v = 0; v < N; v++) {
    uint64_t m = mask[v];
    if (__builtin_popcountll(m) >= 2) {
        uint64_t tmp = m;
        while (tmp) {
            int i = __builtin_ctzll(tmp);
            tmp &= (tmp - 1);
            uint64_t tmp2 = tmp;
            while (tmp2) {
                int j = __builtin_ctzll(tmp2);
                tmp2 &= (tmp2 - 1);
                add_pair(fightRow, i, j);
            }
        }
    }
}

// Edge boundaries
for (int i = 0; i < M; i++) {
    int a = U[i], b = V[i];
    uint64_t ma = mask[a], mb = mask[b];
    if (ma == 0 || mb == 0) continue; // unreachable side

    uint64_t ta = ma;
    while (ta) {
        int ca = __builtin_ctzll(ta);
        ta &= (ta - 1);
        uint64_t others = mb & ~(1ULL << ca);
        uint64_t tb = others;
        while (tb) {
            int cb = __builtin_ctzll(tb);
            tb &= (tb - 1);
            add_pair(fightRow, ca, cb);
        }
    }
}

// Output in lexicographic order
for (int a = 0; a < L; a++) {
    for (int b = a + 1; b < L; b++) {
        if (fightRow[a] & (1ULL << b)) {
            printf("%d %d\n", a, b);
        }
    }
}

free(start); free(U); free(V); free(W);
free(dist); free(mask);
free(heap);
return 0;

}