Subtask 1: $1 \le N, M \le 20$

Ở subtask này, ta duyệt $\mathcal{O}(2^M)$ cách chọn đường bảo trì, sau đó Dijkstra để lựa chọn phương án có đường đi ngắn nhất tới các đỉnh nhỏ nhất và tổng trọng số các con đường là nhỏ nhất.

Độ phức tạp: $\mathcal{O}(M \log N \cdot 2^M)$

Subtask 2: Các con đường có độ dài bằng nhau

Trong subtask này, các con đường có độ dài bằng nhau. Gọi $dist[u]\,(1 \le u \le N)$ là độ dài đường đi ngắn nhất từ $1$ đến $u$. Ta có thể dễ dàng tìm $dist$ trong $O(M)$ bằng BFS.

Ta có cách chọn các con đường tối ưu như sau: với mỗi đỉnh $u\,(1 < u \le N)$, chọn một cạnh kề $u$ bất kì nằm trên đường đi ngắn nhất từ $1$ đến $u$; nói cách khác, ta chọn một cạnh $(v, u)$ bất kì sao cho $dist[v] + c(v, u) = dist[u]$ với $v \neq u, v \in [1, N]$ và $c(v, u)$ là trọng số cạnh $(v, u)$.

Cách làm này cho ta một đồ thị mới với $N-1$ cạnh, và đường đi từ đỉnh $1$ đến mọi đỉnh còn lại đều là đường đi ngắn nhất. Do các cạnh có trọng số bằng nhau, nên $N-1$ là số lượng cạnh tối ưu nhất. Vì nếu ta chọn $< N-1$ cạnh thì đồ thị không liên thông. Vì vậy, cách làm này có tổng trọng số nhỏ nhất.

Độ phức tạp: $\mathcal{O}(N+M)$.

Subtask 3: ràng buộc gốc

Tương tự như subtask 2, ta đi tìm mảng $dist$ bằng thuật toán Dijkstra trong $\mathcal{O}(M\log N)$. Và chọn các cạnh $(v, u)$ sao cho $dist[v] + c(v, u) = dist[u]$ với mỗi $u \in [2, N]$.

Tuy nhiên, trong trường hợp này, trọng số của các cạnh có thể khác nhau. Do đó điều kiện tổng trọng số nhỏ nhất sẽ không được đảm bảo nếu ta chọn cạnh bất kì. Ta có nhận xét sau: việc chọn cạnh $(v, u)$ cho mỗi đỉnh $u$ không làm ảnh hưởng đến độ dài đường đi ngắn nhất của các cạnh còn lại, do nó không ảnh hưởng đến đường đi ngắn nhất đến $u$. Vì vậy, ta sẽ chọn cạnh $(v, u)$ có trọng số nhỏ nhất trong các cạnh thỏa mãn để tối ưu đáp án.

Độ phức tạp: $\mathcal{O}(M\log N)$

Code tham khảo

template<class T> 
bool maximize(T &a, T b) {
    if (a < b) {a = b; return true;}
    return false;
}

/* Main solution */
int n, m;
const int N = 1e5+5;
struct Edge {
    int u, v, c;
};
vector<Edge> edges;
vector<int> adj[N];
ll dist[N];
int lastEdge[N];

void Dijkstra(int start) {
    memset(dist, 0x3f, sizeof dist);
    memset(lastEdge, 0x3f, sizeof lastEdge);
    dist[start] = 0;
    priority_queue<pair<ll, int>> pq;
    pq.push(mp(0, start));
    while (pq.size()) {
        int u; ll du; tie(du, u) = pq.top(); pq.pop();
        if (-du != dist[u]) continue;
        for(int i : adj[u]) {
            int v = edges[i].u^edges[i].v^u;
            // cout << u << ' ' << e.first << ' ' << e.second << '\n';
            if (minimize(dist[v], dist[u] + edges[i].c)) {
                pq.push(mp(-dist[v], v));
                lastEdge[v] = i;
            } else if (dist[v] == dist[u] + edges[i].c && edges[lastEdge[v]].c > edges[i].c) {
                lastEdge[v] = i;
            }
        }
    }
}

void Solve() {
    Dijkstra(1);
    vector<int> ans;
    reu(i, 2, n) ans.pb(lastEdge[i]);
    cout << ans.size() << '\n';
    for(int id : ans) cout << id+1 << ' ';
}