prime + 优先队列优化+ 前向星+贪心

1.首先你要看出这个是个最小生成树，题目描述的可能不太好，还请多多包涵(看不懂就看原题吧）

2，既然是最小生成树，无非不过prime和kruskal,这里题目固定起点从1出发，明显用prime舒服点。

3，几个卡的地方 ：
①不能直接套最小生成树，一个点可以被多个点到达，所以你要考虑先走那条边好，而且只是 简单的先连最短的边的点是不对的

对于prime算法假设起点是A，那么刚开始A，就是一颗树，如果只是简单的把到树最短的边连起来，那么会出出现将这ABCD，4个点连起来要消耗13的能源，但其实更短的是10。
那这么放心的把边连接起来？

这里要利用下题目的条件，只能从维度高的点到维低的点，所以每次贪心的把优先队列中维度最高的点先出队，因为队列中没有别的点比这个最高点维度更高，所以该点只能通过已经有比他维度更高的点达到，所以可以放心的把到这个点的边加上，不用担心它的边的长短，因为这个点一定要这样到达。所以对优先队列排序 以维度高低优先，如果维度一样，按边短的优先。

②如何建图：
N<10^5，M<105所以邻接矩阵建图不可取，那就只能邻接表，但这个指针很麻烦，所以可以用链式前向星(https://blog.csdn.net/acdreamers/article/details/16902023)，然后建图的时候要根据维度判断哪个点是起点，哪个是终点，同维度双向边，否则单向边，这里卡了下内存，所以空间刚好够用就行，别开太大

Prime+优先队列 时间复杂度 在nlogn + m所以可行

我的板子prime板子

#include <bits/stdc++.h>//时间复杂度 nlogn + m 堆中最多n个点 每次堆排序(logn) 最多入堆n次
using namespace std;    //适用于稠密图
const int MAX =100000;

struct point{
    int to,w,next;
    bool operator < (const point &a)   const{
        return w > a.w;
    }
};
point edge[MAX];
bool vis[MAX];
int head[MAX];
int dis[MAX];//到树的距离
int cnt = 0;
int c,m,n;
void addedage(int x,int y,int z){
    edge[++cnt].to = y;
    edge[cnt].w = z;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
priority_queue<point> q;
void prim(void){
    int ans = 0,ct = 0;//记录路径和，生成树拥有点数
    point t;
    t.to = 1;
    t.w = 0;
    dis[0] = 0;//起点到树的距离为0 
    q.push(t);
    
    while(!q.empty()){
        t = q.top();
        q.pop();
        if(vis[t.to])//一个点可能多次入队了
            continue;
        vis[t.to] = true;
        ans+=t.w;//求生成树路径和
      
        if(++ct == n){//判断是否已经 n个点相连，加上了n-1条边
            return;
        }

        for(int i = head[t.to];~i;i = edge[i].next){
            int u = edge[i].to;
            if(!vis[u] && dis[u] > edge[i].w){//边不在树上并且边更短
                dis[u] = edge[i].w;
                t.to = u;
                t.w = dis[u];
                q.push(t);
            }
        }
    }
}

int main(){
    
    while(cin >> c >> m >> n){
        int x,y,z;
        cnt = 0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(dis,0x3f,sizeof(dis));//注意边的范围
        for(int i = 0;i < m;i++){
            cin >> x >> y >> z;
            addedage(x,y,z);
            addedage(y,x,z);
        }
        prim();
    }
    
    //system("pause");
    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
const int MAXE = 200020;
const int MAXV = 100020;
typedef long long ll;

ll dist[MAXV];
bool vis[MAXV];
int head[MAXV];
int vertex[MAXV];
struct point{
    ll to,w,next;
    
};
bool operator < (point ty1,point ty2){
    if( vertex[ty1.to] < vertex[ty2.to]){
            return true;
        }else if( vertex[ty1.to] > vertex[ty2.to]){
            return false;
        }else{
            return ty1.w > ty2.w;
        }
}
point edge[MAXE];
int cnt = 0;
ll n,m;
priority_queue<point> q;
void addedage(int x,int y,int z){
    edge[++cnt].to = y;
    edge[cnt].w = z;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
void prime(int s){
    ll ans = 0,ct = 0;
    
    dist[s] =0;
    point t;
    t.to = s;
    t.w = 0;
    q.push(t);
    
    while(!q.empty()){
        t = q.top();
        q.pop();
        
        if(vis[t.to])
            continue;
        vis[t.to] = true;
        ans+=t.w;
        
        if(++ct == n)
            break;
        for(int i = head[t.to];~i;i = edge[i].next){
            ll u = edge[i].to;
            //cout << u << " " << vis[u] << " " << dist[u] << " " << edge[i].w <<endl;
            if(!vis[u] && dist[u] > edge[i].w){
            
                dist[u] = edge[i].w;
                t.to = u;
                t.w = dist[u];
                q.push(t);
                 //cout << u << endl;
            }
        }
        
    }
   
    printf("%lld %lld\n",ct,ans);
    priority_queue<point> q1;//清空队列
    q = q1;
    return ;
    
}

int main(){
//  freopen("C:\\Users\\86130\\Desktop\\code\\problem\\1.in","r",stdin);
//  freopen("C:\\Users\\86130\\Desktop\\code\\problem\\1.out","w",stdout);
    while(scanf("%lld %lld",&n,&m)!=EOF){
    //  scanf("%lld %lld",&n,&m);
        memset(head,-1,sizeof(head));
        memset(dist,0x3f,sizeof(dist));
        memset(vis,0,sizeof(vis));
        memset(vertex,-1,sizeof(vertex));
        cnt = 0;
        
       
        for(int i = 1;i <= n;i++)
            scanf("%lld",&vertex[i]);
        ll x,y,z;
        for(int j = 0;j < m;j++){
            scanf("%lld %lld %lld",&x,&y,&z);
            if(vertex[x] > vertex[y])
                addedage(x,y,z);
            else if(vertex[x] < vertex[y])
                addedage(y,x,z);
            else{
                addedage(x,y,z);
                addedage(y,x,z);
            }
        }
        
        prime(1);
    }
   // system("pause");
    return 0;
}