思路：题目的大致意思是任意两个QS要互通，每两个QS互通的条件是一条光缆和两个适配器。第一想到的是最小生成树的题，但是有一点不一样，就是题目不仅给了你边权，还给了你点权。转换一下思维就好了，把任意两个QS的边权看成光缆的耗费和两个QS的适配器的耗费即可。
代码：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define inf 0x3f3f3fint edge[1009][1009];int dis[1009];bool vis[1009];int adp[1009]; //适配器的耗费int n;int prime(){ memset(vis,false,sizeof(vis)); int i,j; for(i=1; i<=n; i++) { dis[i]=edge[1][i]; } vis[1]=true; int minc; int p; int ans=0; for(i=2; i<=n; i++) { minc=inf; for(j=1; j<=n; j++) if(!vis[j]&&minc>dis[j]) minc=dis[p=j]; ans+=minc; vis[p]=true; for(j=1; j<=n; j++) { if(!vis[j]&&dis[j]>edge[p][j]) { dis[j]=edge[p][j]; } } } return ans;}int main(){ int t; int i,j; int m; int x,y,w; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1; i<=n; i++) for(j=1; j<=n; j++) edge[i][j]=inf; for(i=1; i<=n; i++) { scanf("%d",&x); adp[i]=x; } for(i=1; i<=n; i++) for(j=1; j<=n; j++) { scanf("%d",&x); edge[i][j]=edge[j][i]=x+adp[i]+adp[j]; //我的思路看懂了就懂了 } int ans=prime(); printf("%d\n",ans); } return 0;}
