Cod sursa(job #3166503)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 8 noiembrie 2023 20:35:36
Problema Barbar Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.63 kb
#include <fstream>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
#include <algorithm>
#define INF (1 << 30)
std::ifstream fin("input.in");
std::ofstream fout("output.out");
std::vector<std::vector<std::pair<int, int>>> V;
std::vector<std::vector<int>> arb[28001];
std::vector<std::pair<int, int>> edges;
std::map<std::pair<int, int>, int> M;
std::vector<int> viz, path, fin_path;
int n, m, x, y, s;
int mxd = -1, start = 1;
void DFS1(int node, int d, const std::vector<std::vector<int>>& tree){
    viz[node] = true;
    if(mxd < d){
        mxd = d;
        start = node;
    }
    for(int it : tree[node]){
        if(!viz[it]){
            DFS1(it, d + 1, tree);
        }
    }
}
int init_mxd, ok;
void DFS2(int node, int d, const std::vector<std::vector<int>>& tree){
    viz[node] = true;
    path.push_back(node);
    if(mxd < d){
        mxd = d;
        if(mxd == init_mxd && !ok){ ok = 1;
            for(auto it : path)
                fin_path.push_back(it);
        }
    }
    for(int it : tree[node]){
        if(!viz[it])
            DFS2(it, d + 1, tree);
    }
    path.pop_back();
}
std::string canonical(int node, int parent, const std::vector<std::vector<int>>& tree){
    std::vector<std::string> child;
    for(int it : tree[node]){
        if(it == parent)
            continue;
        child.push_back(canonical(it, node, tree));
    }
    std::string str = "(";
    std::sort(child.begin(), child.end());
    for(auto it : child){
        str += it;
    }
    str += ")";
    return str;
}
void findMidUtil(const std::vector<std::vector<int>>& tree){
    int minNode = 1;
    mxd = -1, init_mxd = 0;
    for(int i = 1; i <= s; i++)
        if(tree[i].size() % 2)
            minNode = i;
    DFS1(minNode, 1, tree);
     init_mxd = mxd;
    mxd = -1; 
    
    viz = std::vector<int> (n + 1, 0);
    DFS2(start, 1, tree);
}
int config(int u, int v){
    std::string tree1, tree11, tree2;
     ok = 0;
    path = fin_path = std::vector<int> ();
    viz = std::vector<int> (s + 2, 0);
    findMidUtil(arb[u]);
    int L1 = mxd;
    tree1 = canonical(fin_path[fin_path.size() / 2], -1, arb[u]);
    if(fin_path.size() / 2 + 1 < fin_path.size())
        tree11 = canonical(fin_path[fin_path.size() / 2 + 1], -1, arb[u]);
    /*if(fin_path.size() / 2 - 1 < fin_path.size())
        tree111 = canonical(fin_path[fin_path.size() / 2 - 1], -1, arb[u]);*/
    path = fin_path = std::vector<int> ();
    viz = std::vector<int> (s + 2, 0); ok = 0;
    findMidUtil(arb[v]);
    int L2 = mxd;
    if(L1 != L2)
        return false;
    tree2 = canonical(fin_path[fin_path.size() / 2], -1, arb[v]);
    /*if(fin_path.size() / 2 + 1 < fin_path.size())
        tree22 = canonical(fin_path[fin_path.size() / 2 - 1], -1, arb[v]);
    if(fin_path.size() / 2 - 1 < fin_path.size())
        tree222 = canonical(fin_path[fin_path.size() / 2 - 1], -1, arb[u]);*/
    if(tree1 == tree2  || tree11 == tree2)
        return true;
    return false;
}
int dist(int x, int y){
    std::queue<std::pair<int, int>> Q;
    std::vector<int> viz(n + 2), dist(n + 2, INF);
    Q.push({0, x});
    viz[x] = 0;
    dist[x] = 0;
    int lastval = INF;
    while(!Q.empty()){
        int u = Q.front().second;
        if(dist[u] != INF && u == y && lastval > dist[u])
            lastval = dist[u];
        Q.pop();
        for(std::pair<int, int> it : V[u]){
            if(M[std::make_pair(u, it.first)] && dist[it.first] > dist[u] + it.second){
                dist[it.first] = dist[u] + it.second;
                viz[it.first] ++;
                if(viz[it.first] >= n)
                    return -1;
                Q.push({dist[it.first], it.first});
            }
        }    
    }
    return ((lastval == INF) ? -1 : lastval);
}
int main(){
    fin >> n >> m >> x >> y >> s;
    V = std::vector<std::vector<std::pair<int, int>>> (n + 2);
    int u, v, w;
    for(int i = 1; i <= m; i++){
        fin >> u >> v >> w;
        V[u].push_back({v, w});
        edges.push_back({u, v});
    }
    for(int i = 1; i <= n; i++){
        arb[i] = std::vector<std::vector<int>> (s + 1);
        for(int j = 1; j <= s - 1; j++){
            fin >> u >> v;
            arb[i][u].push_back(v);
            arb[i][v].push_back(u);
        }
    }
    for(int i = 0; i < m; i++){
        if(config(edges[i].first, edges[i].second)){
            M[{edges[i].first, edges[i].second}] = 1;
        }
        else M[{edges[i].first, edges[i].second}] = 0;
    }
    int mindist = dist(x, y);
    if(mindist != -1)
        fout << mindist ;
    else 
        fout << "Black hole detected!";
}