`@`$\texttt{Idea}$

`-` Dữ liệu:
`@` d[u]   : thời điểm sớm nhất có quân tới u
`@` ow[u]  : quốc gia tới u sớm nhất
`@` wrc[u] : thành phố u đã xảy ra chiến tranh hay chưa (True/False)
`@` wr     : tập các cặp quốc gia đánh nhau (luôn lưu min, max)
`@` priority queue (time, u, country)

`-` Khởi tạo:
Với mọi u:
    d[u] = INF
    ow[u] = -1
    wrc[u] = False

`-` Multi-source:
Với mỗi quốc gia i tại thành phố c[i]:
    Nếu d[c[i]] == 0 và ow[c[i]] != i:
        wr += (min(i, ow[c[i]]), max(i, ow[c[i]]))
        wrc[c[i]] = True
    Ngược lại:
        d[c[i]] = 0
        ow[c[i]] = i
        push (0, c[i], i) vào pq

`-` Dijkstra:
While pq không rỗng:
    (t, u, a) = pop
    Nếu t != d[u] → continue
    Nếu wrc[u] == True → continue

    Với mỗi cạnh u - v (trọng số w):

        # 1. Gặp nhau trên cạnh
        Nếu ow[v] != -1 và ow[v] != a:
            t1 = d[u]
            t2 = d[v]
            Nếu t1 + w > t2 và t2 + w > t1:
                wr += (min(a, ow[v]), max(a, ow[v]))

        nt = t + w

        # 2. Chưa ai tới v
        Nếu d[v] == INF:
            d[v] = nt
            ow[v] = a
            push (nt, v, a)

        # 3. Gặp nhau tại thành phố v
        Else nếu nt == d[v] và ow[v] != a:
            wr += (min(a, ow[v]), max(a, ow[v]))
            wrc[v] = True

`-` In kết quả:
In tất cả các cặp (a, b) trong wr
với a < b, theo thứ tự tăng dần

Mang tính tham khảo