Subtask 1:

Dễ thấy với ~k = 1~, bài toán tương đương với tìm cây khung nhỏ nhất trên đồ thị vô hướng. Các bạn có thể đọc về các thuật toán tìm cây khung nhỏ nhất tại đây. Lưu ý rằng sau khi tìm được trọng số nhỏ nhất của cây khung, ta cần in ra chi phí sau khi áp dụng khuyến mãi theo yêu cầu đề bài.

Subtask 2:

Ta có thể viết lại công thức tinh chi phí trả cho nhà mạng thứ ~j~ như sau (với ~x_j~ là tổng chi phí các đường dây được chọn thuộc nhà mạng ~j~):

$$ x_j - \frac{\max(0, x_j - s_j)}{2} = \min\left(x_j, x_j - \frac{x_j - s_j}{2}\right) = \min\left(x_j, \frac{x_j + s_j}{2}\right)$$

Do đó với ~k = 2~, ta cần tìm cây khung sao cho giá trị sau là nhỏ nhất:

$$\min\left(x_1, \frac{x_1 + s_1}{2}\right) + \min\left(x_2, \frac{x_2 + s_2}{2}\right) = \min\left(x_1 + x_2, \frac{2x_1 + x_2 + s_2}{2}, \frac{x_1 + 2x_2 + s_1}{2}, \frac{x_1 + x_2 + s_1 + s_2}{2}\right)$$

Trong biểu thức trên, ~s_1~ và ~s_2~ là hằng số. Vậy ta cần tìm ~3~ cây khung:

1. Cây khung có ~x_1 + x_2~ nhỏ nhất. Đây chính là cây khung nhỏ nhất của đồ thị.

2. Cây khung có ~2x_1 + x_2~ nhỏ nhất. Để tìm cây khung này, ta nhân đôi chi phí của tất cả các đường dây thuộc nhà mạng ~1~, sau đó tìm cây khung nhỏ nhất.

3. Cây khung có ~x_1 + 2x_2~ nhỏ nhất. Ta làm tương tự trường hợp thứ hai.

Mỗi cây khung có thể tìm trong độ phức tạp ~O(m \log m)~.

Subtask 3:

Ta mở rộng thuật toán trên với ~k~ bất kì. Cụ thể, ta biến đổi công thức tính chi phí như sau (gọi ~[n]~ là tập hợp các số nguyên từ ~1~ đến ~n~):

$$\sum_{j=1}^{k} \min\left(x_j, \frac{x_j + s_j}{2}\right) = \min\limits_{S \subseteq [n]}\left(\sum\limits_{j \in S} x_j + \sum\limits_{j \in [n] \setminus S} \frac{x_j + s_j}{2}\right) = \frac{1}{2} \min\limits_{S \subseteq [n]}\left(\sum\limits_{j \in S} 2x_j + \sum\limits_{j \in [n] \setminus S} (x_j + s_j)\right)$$

Vậy ta có thể duyệt qua tất cả tập con ~S~ của ~[n]~, nhân chi phí của các đường dây thuộc ~S~ với ~2~ và tìm cây khung nhỏ nhất. Độ phức tạp của thuật toán trên là ~O(2^k m \log m)~, chưa đủ nhanh với giới hạn của subtask 3.

Để tối ưu, ta nhận thấy với mỗi nhà mạng ~j~, ta chỉ cần sử dụng những đường dây thuộc "rừng khung" của nhà mạng ~j~. Do vậy, ta có thể chạy trước thuật toán tìm cây khung nhỏ nhất với mỗi nhà mạng để lọc ra những đường dây cần quan tâm. Mỗi nhà mạng có tối đa ~n - 1~ đường dây quan trọng, do vậy đồ thị sau khi lọc chỉ có ~O(nk)~ cạnh thay vì ~O(m)~ cạnh. Độ phức tạp của thuật toán trở thành ~O(2^k nk \log (nk))~, đủ nhanh để giải subtask 3.

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, pair<int, int>> Edge;

struct DSU {
    int n;
    vector<int> dad;
    DSU(int _n) {
        n = _n;
        dad.assign(n, 0);
        iota(dad.begin(), dad.end(), 0);
    }
    int anc(int u) {
        return dad[u] == u ? u : dad[u] = anc(dad[u]);
    }
    bool join(int u, int v) {
        u = anc(u), v = anc(v);
        if (u == v) return false;
        dad[v] = u;
        return true;
    }
};

int n, m, k;
int t[25];
vector<Edge> comp[25];

long long mst(vector<Edge> &e) {
    sort(e.begin(), e.end());
    vector<Edge> ans;
    long long ret = 0;
    DSU dsu(n);
    for (auto edge: e) {
        int u = edge.second.first, v = edge.second.second, p = edge.first;
        if (dsu.join(u, v)) {
            ans.push_back(edge);
            ret += p;
        }
    }
    e = ans;
    return ret;
}

long long calc(int mask) {
    vector<Edge> e;
    long long spare = 0;
    for (int i = 0; i < k; ++i) {
        if (mask >> i & 1) {
            for (auto edge: comp[i]) {
                edge.first *= 2;
                e.push_back(edge);
            }
        }
        else {
            for (auto edge: comp[i]) e.push_back(edge);
            spare += t[i];
        }
    }
    return mst(e) + spare;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int ntest;
    cin >> ntest;
    while (ntest--) {
        cin >> n >> m >> k;
        for (int i = 0; i < k; ++i) {
            comp[i].clear();
        }
        for (int i = 0; i < m; ++i) {
            int u, v, c, p;
            cin >> u >> v >> c >> p;
            --u, --v, --c;
            comp[c].push_back({p, {u, v}});
        }
        for (int i = 0; i < k; ++i) {
            cin >> t[i];
        }

        for (int i = 0; i < k; ++i) {
            mst(comp[i]);
        }
        long long best = 1e15;
        for (int i = 0; i < (1 << k); ++i) best = min(best, calc(i));
        cout << best << '\n';
    }
    return 0;
}