Submission

Score: 0

User: House123

Problemset: โชว์ของโลมา

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-18 13:32:23

#include <bits/stdc++.h>
using namespace std;

struct edge {
    int u , v , l , r;
    bool operator<(const edge& other) const { 
        return l < other.l;
    }
};
struct DSU {
    vector<int> parent;
    DSU (int i){
        parent.resize(i+1);
        iota(parent.begin(),parent.end(),0);
    }

    int find(int i){
        if(parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int u, int v){
        if(find(u) != find(v)){
            parent[find(u)] = find(v);
        }
    }
};


int main(){
    vector<pair<int,int>> answer;
    ios_base::sync_with_stdio(false), cin.tie(0);
    int b,e; 
    cin >> b >> e;
    vector<edge> edges;
    vector<edge> pending;
    long long total_budget = 0;
    DSU dsu(b);
    for(int i = 0; i < e ; i++){
        int u,v,l,r;
        cin >> u >> v >> l >> r;
        //create adj list first then continue with merging and calculating price in the next loop
        if(r == 1){
            //unite since no fee
            dsu.unite(u,v);
            answer.push_back({u,v});
        } else {
            pending.push_back({u,v,l,r});
        }
        
    }
    sort(pending.begin(),pending.end());
    for(auto &e : pending){
        //if not connect in r == 1, then we will connect it with the shortest path;
        if(dsu.find(e.u) != dsu.find(e.v)){
            dsu.unite(e.u,e.v);
            answer.push_back({e.u,e.v});
            total_budget += e.l;
        }
    }
    cout << total_budget << '\n';
    sort(answer.begin(),answer.end());
    for(auto &i : answer){
        cout << i.first << " " << i.second << '\n';
    }
    return 0;
}