Untitled
unknown
plain_text
a month ago
2.4 kB
4
Indexable
Never
#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; }