Untitled

 avatar
unknown
plain_text
a year ago
2.4 kB
5
Indexable
#include<iostream>
using namespace std;

#define MAXSTACK 10000

class Stack
{
	int top;
	int A[MAXSTACK];
public:
	Stack();
	~Stack();
	void push(int inS);
	int pop();
	bool is_Empty();
	bool is_Full();
	void reset();

private:

};

Stack::Stack()
{
	top = -1;
}

Stack::~Stack()
{
}

bool Stack::is_Empty(){
	if(top == -1) return true;
	return false;
}

bool Stack::is_Full(){
	if(top == MAXSTACK - 1) return true;
	return false;
}

void Stack::push(int inS){
	A[++top] = inS;
}

int Stack:: pop(){
	top--;
	return A[top + 1];
}

void Stack::reset(){
	top = -1;
}

Stack stack;
int Map[100][100];
bool visitedNode[100];
bool visitedEdge[100][100];
int cannon[100];
int countT[100];
int nTestcase, M, M_i, u_i, c_i, nM, result, result_i, currentX, currentY;

int main(){
	freopen("input.txt","r",stdin);
	cin >> nTestcase;
	for(int testcase = 1; testcase <= nTestcase; testcase++){
		cin >> M;

		for(int i = 0; i < M; i++){
			cin >> M_i >> u_i >> c_i;
			cannon[i] = u_i;
			countT[i] = c_i;
			for(int j = 0; j < c_i; j++){
				cin >> Map[i][j];
				visitedEdge[i][j]= visitedEdge[j][i] = false;
			}
			visitedNode[i] = false;
		}
		result = 0;
		currentX = currentY = -1;
		bool checkCircle = false;
		for(int i = 0; i < M; i++){
			for(int k = 0; k < M; k++){
				//
				for(int l = 0; l < countT[k]; l++){
					if(k == currentX && Map[k][l] == currentY){
					
					}else if(k == currentY && Map[k][l] == currentX){
					
					}else{
						visitedEdge[k][l] = false;
					}
				}
				//
				visitedNode[k] = false;
			}
			stack.reset();
			result_i = 100;
			stack.push(i);
			visitedNode[i] = true;
			while(stack.is_Empty() == false && checkCircle == false){
				nM = stack.pop();
				for(int j = 0; j < countT[i]; j++){
					if(visitedEdge[i][j] == false){
						visitedEdge[i][j] = visitedEdge[Map[i][j]][i] = true;
						result_i = (cannon[i] + cannon[Map[i][j]]) < result_i ? (cannon[i] + cannon[Map[i][j]]) : result_i;
						if(visitedNode[j] == false){
							visitedNode[j] = true;
							stack.push(j);
						}else{
							result += result_i;
							currentX = nM;
							currentY = Map[nM][j];
							checkCircle = true;
							break;
						}
					}
				}
			}
		}
		cout << "Case #" << testcase << endl << result << endl;
	}
	return 0;
}