Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.5 kB
1
Indexable
Never
#include<iostream>

using namespace std;

int t, n, a, b, c;

class Stack {
	int top; 
	int arr[1005];
public:
	Stack() {
		top = -1;
	}
	void push(int val) {
		top++;
		arr[top] = val;
	}
	int pop() {
		int val = arr[top];
		top--;
		return val;
	}
	
	bool isempty() {
		return (top == -1);
	}
	void reset() {
		top = -1;
	}
};

Stack q;
int mang[1005][1005], parent[1005],ans, mayBan[1005];
bool visited[1005];

void dfs(int a) {
	q.push(a);
	visited[a] = true;
	while (!q.isempty()) {
		int b = q.pop();
		for (int i = 1; i <= mang[b][0]; i++) {
			if (visited[mang[b][i]]) {
				int temp = parent[mang[b][i]];
				int minDis = mayBan[temp] + mayBan[mang[b][i]];
				while (temp != mang[b][i]) {
					int p = parent[temp];
					if ((mayBan[p] + mayBan[temp]) < minDis)
						minDis = mayBan[p] + mayBan[temp];
					temp = p;
				}
				ans += minDis;
			} else {
				parent[i] = b;
				visited[mang[b][i]] = true;
				q.push(mang[b][i]);
			}
		}
	}
}

int main() {
	//freopen("input.txt","r",stdin);
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a >> b >> c;
			mayBan[a] = b;
			mang[a][0] = c;
			for (int j = 1; j <= c; j++) cin >> mang[a][j];
		}
		ans = 0;
		for (int i = 1; i <= n; i++) {
			q.reset();
			for (int j = 1; j <= n; j++) visited[j] = false;
			dfs(i);
		}
		cout << ans << endl;
	}
	return 0;
}
Leave a Comment