Ai cho em xin ý tưởng bài này với ạ (Dev C++)

This sounds like a really challenging problem! The multi-directional movement and conflict resolution based on timing seems tricky to implement. It almost feels like you need to simulate the war in real-time step-by-step. If you get stuck, maybe try simplifying the rules for a smaller test case first, or even try to kick the buddy of this problem, using brute force to get some initial result, then try optimize later. Good luck, I hope you figure it out!

Nhìn khê thật sự =)))

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;

}

Chào bạn, một người anh em KMA nữa đúng không? Bài toán này là một dạng bài Đa nguồn Dijkstra (Multi-source Dijkstra) kết hợp với việc xử lý các sự kiện va chạm trên cạnh (đường đi) và đỉnh (thành phố).Đây là một bài toán khá hay, yêu cầu tư duy về đồ thị và thời gian rất chặt chẽ. Dưới đây là ý tưởng chi tiết để bạn triển khai trên Dev C++.1. Phân tích bài toánChúng ta có $L$ quốc gia xuất phát từ các đỉnh khác nhau. Tất cả di chuyển với cùng tốc độ. Có hai loại va chạm (chiến tranh) xảy ra:Chiến tranh tại thành phố: Khi các chiến binh từ 2 hoặc nhiều quốc gia đến cùng một thành phố tại cùng một thời điểm $T$ sớm nhất.Chiến tranh trên đường: Khi chiến binh từ quốc gia A đi từ $u$ đến $v$ và quốc gia B đi từ $v$ đến $u$. Họ sẽ gặp nhau trên đường nếu tổng thời gian họ đến hai đầu mút và thời gian di chuyển trên đường cho thấy họ sẽ "đâm" vào nhau.2. Ý tưởng giải thuậtBước 1: Thuật toán Dijkstra đa nguồnBạn cần tìm xem mỗi thành phố $u$ sẽ bị chiếm đóng bởi quốc gia nào và vào thời điểm nào.Sử dụng một mảng min_dist[N] lưu thời gian sớm nhất để một quốc gia đến được thành phố.Sử dụng một mảng owner[N] để lưu danh sách các quốc gia đến thành phố đó tại thời điểm min_dist[N]. Lưu ý: owner[u] nên là một vector hoặc một tập hợp vì có thể có nhiều quốc gia cùng đến một lúc (gây ra chiến tranh tại thành phố).Bước 2: Xác định trạng thái của thành phốSau khi chạy Dijkstra:Nếu owner[u] chỉ có 1 quốc gia: Quốc gia đó chiếm đóng thành phố và tiếp tục đi chinh phạt các lân cận.Nếu owner[u] có từ 2 quốc gia trở lên: Chiến tranh xảy ra tại thành phố $u$. Quan trọng: Theo quy tắc, các quốc gia này sẽ dừng lại tại đây và không đi tiếp từ thành phố này nữa.Bước 3: Xác định các cặp quốc gia chiến đấuChúng ta sẽ duyệt qua tất cả các sự kiện để tìm các cặp $(a, b)$ chiến đấu:Trường hợp 1: Chiến tranh tại thành phố $u$Nếu owner[u].size() > 1, tất cả các cặp quốc gia trong danh sách này sẽ chiến đấu với nhau.Ví dụ: Nếu quốc gia 0, 1, 2 cùng đến thành phố $u$ lúc $T=100$, ta có các cặp: (0, 1), (0, 2), (1, 2).Trường hợp 2: Chiến tranh trên con đường $(u, v)$ có độ dài $w$Duyệt qua mỗi cạnh $(u, v)$ trong $M$ cạnh:Gọi $d[u]$ là thời gian quốc gia $A$ đến $u$, $d[v]$ là thời gian quốc gia $B$ đến $v$.Nếu quốc gia $A$ đến $u$ sớm nhất và đi tiếp sang $v$.Nếu quốc gia $B$ đến $v$ sớm nhất và đi tiếp sang $u$.Họ sẽ gặp nhau trên đường nếu: $d[u] + w > d[v]$ VÀ $d[v] + w > d[u]$.Đặc biệt, nếu $d[u] + w = d[v]$ thì họ gặp nhau tại đúng thành phố $v$ (đã xử lý ở trường hợp 1). Vậy ta chỉ xét khi các chiến binh thực sự chạm mặt giữa đường.3. Các lưu ý về cài đặt (Dev C++)Dữ liệu: Dùng std::priority_queue để cài đặt Dijkstra.Lưu kết quả: Dùng một std::set<std::pair<int, int>> để lưu các cặp chiến tranh. Việc dùng set giúp bạn tự động loại bỏ trùng lặp và giữ các cặp theo thứ tự từ điển (ví dụ luôn lưu cặp $(a, b)$ với $a < b$).Cấu trúc dữ liệu:C++struct Edge { int to, weight; }; vector<Edge> adj[N]; int dist[N]; // Thời gian đến sớm nhất vector<int> owners[N]; // Danh sách quốc gia đến sớm nhất 4. Các bước thực hiện cụ thểKhởi tạo dist[i] = INF, cho tất cả các thành phố $c_i$ của $L$ quốc gia vào Priority Queue với dist[c_i] = 0.Chạy Dijkstra. Lưu ý: Khi lấy một đỉnh $u$ ra khỏi PQ, nếu owners[u].size() > 1 (chiến tranh tại đỉnh), thì không duyệt các đỉnh kề của nó nữa.Sau khi xong Dijkstra, duyệt lại tất cả các đỉnh để tìm chiến tranh tại thành phố.Duyệt tất cả các cạnh để tìm chiến tranh trên đường.In kết quả từ set ra file.Ràng buộc: Với $N, M \le 2000$, thuật toán $O(M \log N)$ của Dijkstra hoàn toàn đáp ứng tốt thời gian.Bạn thử cài đặt theo hướng này nhé, nếu kẹt ở đoạn code nào (như xử lý đa nguồn hoặc lưu cặp) thì cứ hỏi mình!