3号wa求改
查看原帖
3号wa求改
618071
StarSide楼主2024/10/25 20:08
#include<bits/stdc++.h>

using namespace std;
typedef struct Node {
    int weight;
    int vertex;
} Node;
int lowcost[10011];
int ans = 0;
vector<Node> G[10011];
int v, e;

void prim(vector<Node> g[], int x) {
    for (int i = 1; i <= v; i++) {
        lowcost[i] = 100000;
    }
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i].vertex;
        int w = g[x][i].weight;
        lowcost[y] = w;
    }
    lowcost[x] = 0;
    for (int cnt = 1; cnt < v; cnt++) {
        int Min = 100000, k = x;
        for (int i = 1; i <= v; i++) {
            if (lowcost[i] < Min && lowcost[i] != 0) {
                Min = lowcost[i];
                k = i;
            }
        }
        ans += Min;
        lowcost[k] = 0;
        x = k;

        for (int j = 0; j < g[x].size(); j++) {
            int y = g[x][j].vertex;
            int w = g[x][j].weight;
            if (lowcost[y] > w) {
                lowcost[y] = w;
            }
        }
    }
}

int main() {
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        Node n;
        n.vertex = x, n.weight = w;
        G[y].push_back(n);
        n.vertex = y, n.weight = w;
        G[x].push_back(n);
    }
    prim(G, 1);
    for (int i = 1; i <= v; i++) {
        if (lowcost[i] == 100000) {
            cout << "orz";
            return 0;
        }
    }
    cout << ans;
}

2024/10/25 20:08
加载中...