题目描述

水个题解：我指一种正确的思路错误的求和;
原本想着是拿找父节点变true防重来着，
但是会出现靠近1的节点边被重复计算的问题，如//中所示;
所以最正确的做法是简单的边相加;

样例

#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int N,M;
int e[400000],ne[400000],c[400000],idx;
int D[30000];
int P[30000],L[30000],xb[30000];
int dis[30000];
bool st[30000];
void add(int a,int b,int co){
    e[idx]=b,c[idx]=co,ne[idx]=D[a],D[a]=idx++;
}
bool ok(int a,int b){
    return  dis[a]>dis[b];
}
void dj(){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> qe;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    qe.push({0,1});

    while(qe.size()){
        auto m=qe.top();
        qe.pop();

        int a=m.first,b=m.second;
        if(st[b])continue;
        st[b]=true;

        for(int i=D[b];i!=-1;i=ne[i]){
            int p=e[i];
            if(dis[p]>dis[b]+c[i]){
                dis[p]=dis[b]+c[i];
                P[p]=b;
                L[p]=c[i];
                qe.push({dis[p],p});
            }
            else if(dis[p]==dis[b]+c[i]){
                if(c[i]<L[p])L[p]=c[i],P[p]=b;
            }
        }
    }

    memset(st,false,sizeof(st));

    for(int i=1;i<=N;i++){
        xb[i]=i;
    }

    sort(xb+1,xb+1+N,ok);
    int res=0;
    // for(int i=1;i<=N;i++){
    //     int o=xb[i];
    //     if(st[o])continue;
    //     st[o]=true;
    //     res+=dis[o];
    //     while(o!=1){
    //         o=P[o];
    //         st[o]=true;
    //     }
    // }
    for(int i=N;i>=2;i--){
        res+=L[i];
    }
    cout<<res;
}
int main(){
    cin>>N>>M;
    memset(D,-1,sizeof(D));
    for(int i=1;i<=M;i++){
        int x,y,co;
        cin>>x>>y>>co;
        add(x,y,co);
        add(y,x,co);
    }
    dj();
}