解题思路

题目很明确，最少的花费就是最小生成树的权值，我选择prim算法求最小生成树，比较简单，套板子主要理解prim里面的两栖边的意义。prim理解起来就不难了。

//无向图最小生成树
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 3e3 + 7;
const int INF = 0x3f3f3f3f;
int e[N][N], vis[N], dis[N];
int n, m;
ll ans;
//prim适合稠密图 O(n^2)，特别是完全图最小生成树的求解
void prim() {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    for (int i = 1; i < n; ++i) {
        int x = 0;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && (x == 0 || dis[j] < dis[x]))
                x = j;
        vis[x] = 1;
        for (int j = 1; j <= n; ++j)//用u点更新  刚刚新拓展的边
            if (!vis[j])    dis[j] = min(dis[j], e[x][j]);
    }
}

int main() {
    int c;
    while (cin >> c >> m >> n) {
        //构建邻接矩阵
        memset(e, 0x3f, sizeof(e));
        for (int i = 0; i <= n; ++i)    e[i][i] = 0;
        for (int i = 1; i <= m; ++i) {
            int x = read(), y = read(), z = read();
            e[x][y] = e[y][x] = min(e[x][y], z);
        }
        //求最小生成树
        prim();
        for (int i = 2; i <= n; ++i)    ans += dis[i];
        if (c < ans)    puts("No");
        else puts("Yes");
    }
    return 0;
}