记录编号	604999	评测结果	AWAAAAATTT
题目名称	2453.次小生成树	最终得分	60
用户昵称	我也不知道	是否通过	未通过
代码语言	C++	运行时间	7.732 s
提交时间	2025-08-13 12:21:51	内存使用	12.04 MiB

    #include <bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> PII; //一对儿需关联的数据<first,second>
    const int N =200001;
    //定义顶点数上限常量N
    int d[N]={0x3f3f3f},pre[N],zhi[N],qqq=1,quan[N]={0};
    //定义存距离MST的最短边数组d[]和parent[]存v加入MST时的前驱u
    int n, m;
    int inMST[N];
    //定义点是否加入MST集合的标记数组inMST[]
     
    struct Edge {//边
    	int to, w;
    };
     
    vector<Edge> g[N];//每个点一个vector，存储该点相连的边 <to,w>
     
    int pq_prim(int s) {
    	priority_queue<PII,vector<PII>,greater<PII> > q;//空队列
    memset(d,0x3f,sizeof(d));
    memset(inMST,0,sizeof(inMST));
    memset(pre,0,sizeof(pre));
    d[s]=0;
    q.push(make_pair(d[s],s));
    int sum=0;
    	for(int i=1;i<=n;i++){
    	    d[i]=1e8; 
            pre[i]=0;
            inMST[i]=pre[i];
    	      d[s]=0;
        }
        while(!q.empty()){
            int u=q.top().second;
            q.pop();
            if(inMST[u]) continue;
            inMST[u]=1;
            sum+=d[u];
            zhi[qqq]=d[u];
            qqq++;
            for(int i=0;i<g[u].size();i++){
                int v=g[u][i].to;
                int w=g[u][i].w;
                if(!inMST[v]&&d[v]>w){
                    d[v]=w;
                    pre[v]=u;
                    q.push(make_pair(d[v],v));
                }
            }
        }
    	return sum;//MST边权值之和
    }
     
    int main() {
    	freopen("secmst.in", "r", stdin);
    	freopen("secmst.out", "w", stdout);
    	cin >> n >>m;
    	int sum = 0;
    	for (int i = 1; i <= m; i++) {
    	        int w,u,v;
    		cin >> u>>v>>w;
    		quan[i]=w;
    		g[u].push_back({v,w});
    		g[v].push_back({u,w}); //无向图
    	
    }
    	int ans = pq_prim(1),www=0x3f3f3f3f;
    	for(int j=1;j<=m;j++){
    	for(int i=1;i<=qqq;i++){
          if(quan[j]-zhi[i]>0) www=min(www,quan[j]-zhi[i]);
     }
    }
    	cout << ans+www << endl;
    	return 0;
    }