C 本地答案正确 lg评测全是orz
查看原帖
C 本地答案正确 lg评测全是orz
36655
蚂蚁的头皮屑楼主2022/10/18 09:22
#include "stdio.h"
#include "stdlib.h"
#define maxe 5003
#define maxst 200005
#define INF 200000000
typedef enum Bool{
    True = 1, 
    False = 0
}bool;

struct edge{
    int v;
    int w;
    int next;
}e[maxst];
int n, m, cnt, pre[maxe];
long ans;
bool vis[maxe];

void add_edge(int u, int v, int w){
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = pre[u];
    pre[u] = cnt;
}

void init(){
    int u, v, w;
    scanf("%d%d", &n, &m); 
    for (int sta = 1; sta <= m; sta++){
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
}

void build_tree_of_least_edgew(){
    vis[1] = 1;
    int dis[maxe];
    int j = pre[1], tot, now = 1, now_dis;
    for (int i = 1; i <= n; i++) dis[i] = INF;
    
    while (j){
        if (e[j].w < dis[e[j].v]) dis[e[j].v] = e[j].w;
        j = e[j].next;
    }//第一个点入树
    
    while(++tot < n){
        now_dis = INF;
        for(int i = 1; i <= n; i++){//枚举每一个点到部分最小生成树的最小距离
            if (!vis[i]&&dis[i] <= now_dis) { now_dis = dis[i]; now = i; } 
        }
        vis[now] = 1; ans+= now_dis;
        j = pre[now];
        while (j){
            if (e[j].w < dis[e[j].v]) dis[e[j].v] = e[j].w;
            j = e[j].next;
        }//将 与新加入的点 相连的边包含进考虑范围
        
        
    }//将剩余几点入树
}

int main() {
    init();
    build_tree_of_least_edgew();
    bool All = 1;
    for (int k = 1; k <= n; k++) if (!vis[k]) All = 0;
    if(All==1) printf("%ld\n", ans);
    else printf("orz");
    return 0;
}
2022/10/18 09:22
加载中...