题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1586
题意是GF读懂的，我是个码手……做法是将边上两点adapter的费用加到边权上跑一遍最短路。题干里只给出了点数不超过1000个，并没有直接给出边的数量。所以要以完全图情况来考虑（直接开1000*1000+的边数组）。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 typedef struct E { 23 int u; 24 int v; 25 int w; 26 }E; 27 28 const int maxn = 1111; 29 int n, m, vv; 30 int a[maxn]; 31 int pre[maxn]; 32 E e[maxn*maxn]; 33 34 bool cmp(E e1, E e2) { 35 return e1.w < e2.w; 36 } 37 38 void init() { 39 m = 0; 40 for(int i = 0; i < maxn; i++) { 41 pre[i] = i; 42 } 43 } 44 45 int find(int x) { 46 return x == pre[x] ? x : pre[x] = find(pre[x]); 47 } 48 49 bool unite(int x, int y) { 50 x = find(x); 51 y = find(y); 52 if(x != y) { 53 pre[x] = y; 54 return 1; 55 } 56 return 0; 57 } 58 59 int main() { 60 // freopen("in", "r", stdin); 61 int T; 62 scanf("%d", &T); 63 while(T--) { 64 init(); 65 scanf("%d", &n); 66 for(int i = 0; i < n; i++) { 67 scanf("%d", &a[i]); 68 } 69 for(int i = 0; i < n; i++) { 70 for(int j = 0; j < n; j++) { 71 scanf("%d", &vv); 72 e[m].u = i; 73 e[m].v = j; 74 e[m++].w = vv + a[i] + a[j]; 75 } 76 } 77 // for(int i = 0; i < m; i++) { 78 // printf("%d ", e[i].w); 79 // } 80 // printf(" "); 81 sort(e, e+m, cmp); 82 int ans = 0; 83 for(int i = 0; i < m; i++) { 84 if(unite(e[i].u, e[i].v)) { 85 ans += e[i].w; 86 } 87 } 88 printf("%d ", ans); 89 } 90 return 0; 91 }