Untitled

 avatar
user_2087184
plain_text
a month ago
1.6 kB
0
Indexable
Never
#include <iostream>
using namespace std;

int a[101][101], l[101], r[101], n, vert, result;
int vt[101], p[101], parent[101], process[101];
const int temp = 10;

void DFS(int k, int s, int cur, int min) {
	if (cur > 1 && k != s) {
		bool hasGoal = false;
		for (int i = 0; i < l[s]; i++) {
			if (a[s][i] == k)	hasGoal = true;
		}
		if (hasGoal) {
			parent[k] = s;
			p[cur + 1] = k;
			p[cur] = s;

			int rTemp = r[s] + r[k];
			int minT = rTemp < min ? rTemp : min;
			result += minT;

			for (int j = 0; j <= cur; j++) {
				cout << p[j] << " ";
			}
			cout << k << " " << endl;
			return;
		}
	}
	for(int i = 0; i < l[s]; i++) {
		int next = a[s][i];
		for (int j = 0; j <= cur; j++) {
			if (p[j] == next && next != k && parent[s] != next) {
				//cout << s << endl;
				return;
			}
		}
		if (vt[next] != -1 && (vt[next] != k + temp || (parent[next] != s && process[s] != 1))) {
			p[cur] = s;
			vt[next] = k + temp;
			int rTemp = r[s] + r[next];
			int minT = rTemp < min ? rTemp : min;
			parent[next] = s;
			process[next] = 1;
			DFS(k, next, cur + 1, minT);
			process[next] = 0;
		}
	}
}

int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> vert >> r[i] >> l[i];
			for(int j = 0; j < l[i]; j++) {
				cin >> a[i][j];
			}
		}
		for (int i = 0; i < n; i++) {
			vt[i] = 0;
			p[i] = 0;
		}
		result = 0;
		for (int i = 0; i < n; i++) {
			vt[i] = -1;
			DFS(i, i, 0, 100000);
		}
		cout << result << endl;
	}
}
Leave a Comment