1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
|
#include <iostream> #include <set> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int N = 1e7 + 5; int pre[N], ran[N], n, m, k, a[N]; struct { int u, v, cost; friend bool operator < (Node e1, Node e2) { return e1.cost>e2.cost; } }node[N]; priority_queue<Node, vector<Node> > q; void init() { while(!q.empty()) q.pop(); for (int i = 1; i <= n;i++) { pre[i] = i; } } int Find(int x) { if(x==pre[x]) return x; else return pre[x] = Find(pre[x]); } int krs() { int ans = 0; while(!q.empty()) { Node u = q.top(); q.pop(); int x = u.u, y = u.v, cost = u.cost; int fx = Find(x); int fy = Find(y); if(fx!=fy) { pre[fx] = fy; ans += cost; } } int cnt = 0; for (int i = 1; i <= n;i++) if(Find(i)==i) cnt++; if(cnt>1) return -1; else return ans; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d%d", &n, &m, &k); init(); for (int i = 1; i <= m;i++) { Node temp; scanf("%d%d%d", &temp.u, &temp.v, &temp.cost); q.push(temp); } while(k--) { int s; scanf("%d", &s); for(int i=1; i<=s; i++) { scanf("%d", &a[i]); if(i>1) { Node temp; temp.u = a[i - 1]; temp.v = a[i]; temp.cost = 0; q.push(temp); } } } cout << krs() << endl; } }
|
近期评论