//普通邻接矩阵 时间复杂度 O(v*e)
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define INF 999999
int v;
int map[505][505];
int lowcost[505];
int visit[1000];
int prim( int start )
{int min, choose, ans;ans = 0;for( int i = 1; i <= v; i++ ){lowcost[i] = map[start][i];}lowcost[start] = 0;visit[start] = 1;for( int i = 1; i <= v-1; i++ ){min = INF;for( int j = 1; j <= v; j++ ){if( !visit[j] && lowcost[j] >= 0 && lowcost[j] < min ){min = lowcost[j];choose = j;}}ans += lowcost[choose];visit[choose] = 1;for( int j = 1; j <= v; j++ ){if( !visit[j] && map[choose][j] < lowcost[j] )lowcost[j] = map[choose][j]; }}return ans;
}
int main( )
{int T, e, min, a, b, w, num;scanf( "%d", &T );while( T-- ){memset( map, 0, sizeof(map) );memset( visit, 0, sizeof(visit) );memset( lowcost, -1, sizeof(lowcost) ); scanf( "%d%d", &v, &e );for( int i = 0; i < e; i++ ){scanf( "%d %d %d\n", &a, &b, &w );if( map[a][b] ){if( map[a][b] > w ){map[a][b] = w;map[b][a] = w;}}else{map[a][b] = w;map[b][a] = w;}}min = INF;for( int i = 0; i < v; i++ ){scanf( "%d", &num );if( num < min )min = num;}printf( "%d\n", min+prim( 1 ) ); }return 0;
}
优先队列+邻接矩阵 优先队列 时间复杂度 O( nlog(n) )
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define MAX 505
#define INF 9999999
#define CLR(arr,val) memset(arr,val,sizeof(arr))using namespace std;
typedef struct a
{int dis, v;friend bool operator < ( const struct a &n1, const struct a &n2 ){return n1.dis > n2.dis;}
}node;
int n;
int map[MAX][MAX];
int vis[MAX];
int lowcost[MAX];
inline void init()
{for( int i = 0; i < MAX; i++ ){lowcost[i] = INF;for( int j = 0; j < MAX; j++ )map[i][j] = INF;}CLR( vis, 0 );
};
int prim( int start )
{int sum = 0;node pre, cur;priority_queue<node> Q;lowcost[start] = 0;pre.dis = 0;pre.v = start;Q.push( pre );while( !Q.empty() ){pre = Q.top();Q.pop();if( vis[pre.v] )continue;sum += pre.dis;vis[pre.v] = 1;for( int i = 1; i <= n; i++ ){if( !vis[i] && map[pre.v][i] < lowcost[i] ){lowcost[i] = map[pre.v][i];cur.dis = lowcost[i];cur.v = i;Q.push( cur );}}}return sum;
}
int main()
{int T, e, a, b, w, num, min;scanf( "%d", &T ); while( T-- ) { init();scanf( "%d%d", &n, &e ); for( int i = 0; i < e; i++ ) { scanf( "%d %d %d\n", &a, &b, &w ); if( map[a][b] ) { if( map[a][b] > w ) { map[a][b] = w; map[b][a] = w; } } else { map[a][b] = w; map[b][a] = w; } } min = INF; for( int i = 0; i < n; i++ ) { scanf( "%d", &num ); if( num < min ) min = num; } printf( "%d\n", prim( 1 ) + min );}return 0;
}