解题关键：注意下标
解法一：prim算法
1 #include<bits/stdc++.h> 2 #define maxv 1002 3 #define maxm 50002 4 #define INF 0x3f3f3f3f 5 using namespace std; 6 typedef long long ll; 7 int cost[maxv][maxv]; 8 int mincost[maxv]; 9 bool used[maxv]; 10 int V; 11 12 int prim(){ 13 fill(mincost,mincost+V,INF); 14 mincost[0]=0; 15 int res=0; 16 17 while(true){ 18 int v=-1; 19 for(int u=0;u<V;u++){ 20 if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u; 21 } 22 if(v==-1) break; 23 used[v]=true; 24 res+=mincost[v]; 25 for(int u=0;u<V;u++){ 26 mincost[u]=min(mincost[u],cost[v][u]); 27 } 28 } 29 return res; 30 } 31 int main(){ 32 for(int i=0;i<maxv;i++){ 33 for(int j=0;j<maxv;j++){ 34 cost[i][j]=INF; 35 } 36 } 37 int n,m,t1,t2,t3; 38 cin>>n>>m; 39 V=n; 40 for(int i=0;i<m;i++){ 41 cin>>t1>>t2>>t3; 42 cost[t1-1][t2-1]=cost[t2-1][t1-1]=t3; 43 } 44 int ans=prim(); 45 cout<<ans<<endl; 46 }