StarDust

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

int n, m, x, y, s, viz[1001], nr[1001], d[1001];
vector<pair<int, pair<int, int>>> edges;
vector<int> arb[1001][101];
vector<int> tree[201], subtreeLabels[201], children[201];
vector<int> L[101], pred;

bool compare(int a, int b) {
    return subtreeLabels[a] < subtreeLabels[b];
}

bool equals(int a, int b) {
    return subtreeLabels[a] == subtreeLabels[b];
}

vi findCenter(int offset = 0) {
    int cnt = n;
    vi a;
    vi deg(n);
    for (int i = 0; i < n; i++) {
        deg[i] = tree[i + offset].size();
        if (deg[i] <= 1) {
            a.push_back(i + offset);
            --cnt;
        }
    }

    while (cnt > 0) {
        vi na;
        for (int i = 0; i < (int) a.size(); i++) {
            int u = a[i];
            for (int j = 0; j < (int) tree[u].size(); j++) {
                int v = tree[u][j];
                if (--deg[v - offset] == 1) {
                    na.push_back(v);
                    --cnt;
                }
            }
        }
        a = na;
    }
    return a;
}

int dfs(int u, int p = -1, int depth = 0) {
    L[depth].push_back(u);
    int h = 0;
    for (int i = 0; i < (int) tree[u].size(); i++) {
        int v = tree[u][i];
        if (v == p)
            continue;
        pred[v] = u;
        children[u].push_back(v);
        h = max(h, dfs(v, u, depth + 1));
    }
    return h + 1;
}

bool rootedTreeIsomorphism(int r1, int r2) {
    for(int i = 0; i < n; i++) {
        L[i].clear();
    }
    for(int i = 0; i < 2 * n; i++) {
        pred.push_back(-1);
    }
    for(int i = 0; i < 2 * n; i++) {
        children[i].clear();
    }
    //children.assign(2 * n, vi());

    int h1 = dfs(r1);
    int h2 = dfs(r2);
    if (h1 != h2)
        return false;

    int h = h1 - 1;
    vi label(2 * n);
    for(int i = 0; i < 2 * n; i++) {
        subtreeLabels[i].clear();
    }
    //subtreeLabels.assign(2 * n, vi());

    for (int i = h - 1; i >= 0; i--) {
        for (int j = 0; j < (int) L[i + 1].size(); j++) {
            int v = L[i + 1][j];
            subtreeLabels[pred[v]].push_back(label[v]);
        }
        for (int j = 0; j < (int) L[i].size(); j++) {
            int v = L[i][j];
            sort(subtreeLabels[v].begin(), subtreeLabels[v].end());
        }

        sort(L[i].begin(), L[i].end(), compare);

        for (int j = 0, cnt = 0; j < (int) L[i].size(); j++) {
            if (j && !equals(L[i][j], L[i][j - 1]))
                ++cnt;
            label[L[i][j]] = cnt;
        }
    }

    if (!equals(r1, r2))
        return false;
    return true;
}

bool treeIsomorphism() {
    vi c1 = findCenter();
    //c1.push_back(0);
    vi c2 = findCenter(n);
    if (c1.size() == c2.size()) {
        if (rootedTreeIsomorphism(c1[0], c2[0]))
            return true;
        else if (c1.size() > 1)
            return rootedTreeIsomorphism(c1[1], c2[0]);
    }
    return false;
}

bool izo(int p, int q) {
    for(int i = 0; i < 2 * n; i++) {
        tree[i].clear();
    }
    //tree.assign(2 * n, vi());
    for (int u = 0; u < n; u++) {
        for (int i = 0; i < (int)arb[p][u].size(); i++) {
            int v = arb[p][u][i];
            tree[u].push_back(v);
        }
        for (int i = 0; i < (int)arb[q][u].size(); i++) {
            int v = arb[q][u][i];
            tree[u + n].push_back(v + n);
        }
    }
    return treeIsomorphism();
}

int main()
{
    ifstream f("stardust.in");
    ofstream g("stardust.out");
    f >> s >> m >> x >> y >> n;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        f >> u >> v >> w;
        edges.push_back(make_pair(w, make_pair(u, v)));
    }
    for(int j = 1; j <= s; j++) {
        d[j] = 1e9;
        for(int i = 1; i < n; i++) {
            int u, v;
            f >> u >> v;
            u--; v--;
            //cout << u << v << '\n';
            arb[j][u].push_back(v);
            arb[j][v].push_back(u);
        }
        //cout << '\n';
    }
    viz[x] = 1;
    for(int i = 1; i <= s; i++) {
        viz[i] = izo(x, i);
        //cout << viz[i] << '\n';
    }
    d[x] = 0;
    for(int i = 1; i < s; i++) {
        for(int j = 0; j < m; j++) {
            int n1 = edges[j].second.first;
            int n2 = edges[j].second.second;
            int c = edges[j].first;
            if(viz[n2] && d[n1] != 1e9 && d[n1] + c < d[n2]) {
                d[n2] = d[n1] + c;
            }
        }
    }
    for(int j = 0; j < m; j++) {
        int n1 = edges[j].second.first;
        int n2 = edges[j].second.second;
        int c = edges[j].first;
        if(viz[n2] && d[n1] != 1e9 && d[n1] + c < d[n2]) {
            g << "Black hole detected!";
            return 0;
        }
    }
    g << d[y];
    return 0;
}