結果

問題 No.2630 Colorful Vertices and Cheapest Paths
ユーザー GOTKAKO
提出日時 2024-02-16 22:30:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 872 ms / 2,500 ms
コード長 1,691 bytes
コンパイル時間 2,309 ms
コンパイル使用メモリ 209,328 KB
最終ジャッジ日時 2025-02-19 14:16:05
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class UnionFind{
    public:
    vector<int> par,siz;
 
    void make(int N){
        par.resize(N,-1);
        siz.resize(N,1);
    }
 
    int root(int x){
        if(par.at(x) == -1) return x;
        else return par.at(x) = root(par.at(x));
    }
 
    void unite(int u, int v){
        u = root(u),v = root(v);
        if(u == v) return;
        if(siz.at(u) < siz.at(v)) swap(u,v);
 
        par.at(v) = u;
        siz.at(u) += siz.at(v);
    }
 
    bool issame(int u, int v){
        if(root(u) == root(v)) return true;
        else return false;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M; cin >> N >> M;

    vector<vector<int>> Graph(N);
    for(int i=0; i<M; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }
    vector<int> C(N);
    vector<long long> W(10);
    for(auto &c : C) cin >> c,c--;
    for(auto &w : W) cin >> w;
    vector<long long> cost(1024);
    vector<UnionFind> UF(1024);
    for(int i=0; i<1024; i++){
        UnionFind &uf = UF.at(i);
        uf.make(N); 
        for(int k=0; k<N; k++){
            if(!(i&(1<<C.at(k)))) continue;
            for(auto to : Graph.at(k)) if(i&(1<<C.at(to))) uf.unite(k,to);
        }
        for(int k=0; k<10; k++) if(i&(1<<k)) cost.at(i) += W.at(k);
    }

    int Q; cin >> Q;
    for(int i=0; i<Q; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        long long now = 1e18;
        for(int k=0; k<1024; k++) if(UF.at(k).issame(u,v)) now = min(now,cost.at(k));
        if(now == 1e18) now = -1;
        cout << now << endl;
    }
}
0