Language: C++

#include<iostream>
#include <vector>
#include <cassert>

using namespace std;
typedef long long ll;

struct edge {
    int node1;
    int node2;
    int cost;
    bool mst = false;
    int diff = -1;

    edge(int node1_, int node2_, int cost_){
        node1 = node1_;
        node2 = node2_;
        cost = cost_;
    }
};

class UnionFind {
    int n;
    vector<int> roots;
    vector<int> depth;

public:
    UnionFind(int n_){
        n = n_;
        depth.clear(); depth.resize(n);
        roots.clear(); roots.resize(n);

        for (int i = 0; i < n_; i++) {
            roots[i] = i;
            depth[i] = 0;
        }
    }

    void unite(int i, int j){
        int di = depth[find(i)];
        int dj = depth[find(j)];

        if (di > dj){
            roots[find(j)] = find(i);
        } else {
            roots[find(i)] = find(j);
            if (di == dj){
                depth[j] += 1;
            }
        }
    }

    int find(int i){
        if (roots[i] == i){
            return i;
        } else {
            int root = find(roots[i]);
            roots[i] = root;
            return root;
        }
    }

    bool same(int i, int j){
        return find(i) == find(j);
    }
};

const int MOD = 1000000007;
const int MAX_N = 1000;
vector<edge> edges;
vector< vector<int> > G(MAX_N, vector<int>(0));
bool visited[MAX_N];

int dfs(int from, int dest, int maxCost){
    visited[from] = true;
    if (from == dest){
        return maxCost;
    } else {
        for (int i = 0; i < G[from].size(); i++){
            edge e = edges[G[from][i]];
            if (e.mst){
                int to = (e.node1 != from) ? e.node1 : e.node2;
                if (!visited[to]){
                    int ret = dfs(to, dest, max(maxCost, e.cost));
                    if (ret != -1){
                        return ret;
                    }
                }
            }
        }
        return -1;
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    int X;
    cin >> X;

    for (int i = 0; i < M; i++){
        int node1, node2, cost;
        cin >> node1 >> node2 >> cost;
        node1--; node2--;

        edge e = edge(node1, node2, cost);
        edges.push_back(e);
        G[node1].push_back(i);
        G[node2].push_back(i);
    }

    vector< pair<int,int> > costs;
    for (int i = 0; i < M; i++){
        costs.push_back(make_pair(edges[i].cost, i));
    }
    sort (costs.begin(),costs.end());

    int mstCost = 0;
    UnionFind uf = UnionFind(N);
    for (int i = 0; i < M; i++){
        pair<int, int> p = costs[i];

        int node1 = edges[p.second].node1;
        int node2= edges[p.second].node2;

        if (!uf.same(node1, node2)){
            edges[p.second].mst = true;
            uf.unite(node1, node2);
            mstCost += p.first;
        }
    }
//    cout << mstCost << endl;

    for (int i = 0; i < M; i++){
        int from = edges[i].node1;
        int dest = edges[i].node2;

        fill(visited, visited+N, false);
        if (!edges[i].mst){
            int detour = dfs(from, dest, 0);
            assert (detour != -1);
            edges[i].diff = edges[i].cost - detour;
            assert (edges[i].diff >= 0);
        }
    }

//    for (int i = 0; i < M; i++){
//        edge e = edges[i];
//        cout << e.node1 << "," << e.node2 << "," << e.diff << endl;
//    }

    int ret;
    if (X < mstCost){
        ret = 0;
    } else if (X == mstCost){
        int cnt = N - 1; // tree size;
        for (int i = 0; i < M; i++){
            if (edges[i].diff == 0){
                cnt++;
            }
        }

        ret = 1;
        for (int i = 0; i < cnt; i++){
            ret *= 2;
            ret %= MOD;
        }
        ret -= 2;
        for (int i = 0; i < N-cnt; i++){
            ret *= 2;
            ret %= MOD;
        }
    } else {
        int D = X - mstCost;
        assert (D > 0);

        int a = 0, b = 0, c = 0;
        for (int i = 0; i < M; i++){
            if (edges[i].diff < D){
                a++;
            } else if (edges[i].diff == D){
                b++;
            } else {
                c++;
            }
        }

        ret = 1;
        for (int i = 0; i < b; i++){
            ret *= 2;
            ret %= MOD;
        }
        ret -= 1;
        ret *= 2; //for a
        for (int i = 0; i < c; i++){
            ret *= 2;
            ret %= MOD;
        }
    }
    cout << ret << endl;

    return 0;
}



Compiler output:
a.cc: In function 'int main()':
a.cc:116:5: error: 'sort' was not declared in this scope; did you mean 'short'?
  116 |     sort (costs.begin(),costs.end());
      |     ^~~~
      |     short