prim 求最小生成树（邻接表）

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int INF=0x3f3f3f3f;//无穷数
const int maxn=1e5+5;//最大边数；
struct ac{
         
  //to city
    int v,dis;
};
vector<ac> adj[maxn];//data
int n,dis[maxn];//dis 每个点距当前树的距离
bool vst[maxn]={
         
  false};
int re=0;//最终最小花费
void prime(int x){
    memset(dis, INF, sizeof(dis));
    dis[x]=0;
    for(int i=1;i<=n;i++){
         
  //每循环一次加入一个，共n次
        int u=-1,min=INF;
        for(int j=1;j<=n;j++){
            if(vst[j]==false&&dis[j]<min){
                u=j;
                min=dis[j];
            }
        }
        vst[u]=true;
        re+=min;
        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j].v;
            if(vst[v]==false&&adj[u][j].dis<dis[v]){
                dis[v]=adj[u][j].dis;
            }
        }
    }
}
int main(){
    cin>>n;int h;ac data;
    for(int i=1;i<=n;i++){
        cin>>h;//连接到h个城市
        for(int j=0;j<h;j++){
            cin>>data.v>>data.dis;
            adj[i].push_back(data);
        }

    }
    prime(1);
    cout<<re<<endl;


}
/*//共6个城市，第1个城市连接3个城市，城市n 及 花费
 6
 3  2 6 3 1 4 5
 3  1 6 3 5 5 3
 5  1 1 4 5 6 4 5 6 2 5
 3  1 5 3 5 6 2
 3  3 6 2 3 6 6
 3  3 4 4 2 5 6
 *///re 15