Untitled
unknown
plain_text
a year ago
1.5 kB
7
Indexable
#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; }
Editor is loading...
Leave a Comment