結果

問題 No.2630 Colorful Vertices and Cheapest Paths
コンテスト
ユーザー GOTKAKO
提出日時 2024-02-16 22:24:40
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,814 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,570 ms
コンパイル使用メモリ 208,856 KB
最終ジャッジ日時 2025-02-19 14:11:12
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
    UnionFind Z; Z.make(N);
    vector<vector<int>> Graph(N);
    for(int i=0; i<M; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Z.unite(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;

    int Q; cin >> Q;
    for(int i=0; i<Q; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        if(Z.issame(u,v) == false){cout << -1 << endl; return 0;}

        long long now = 1e18;
        vector<bool> visited(N);
    auto dfs = [&](auto dfs,int pos,int W2,long long cost) -> void {
        if(pos == v){now = min(cost,now); return;}
        if(cost >= now) return;

        visited.at(pos) = true;
        for(auto to : Graph.at(pos)){
            if(visited.at(to)) continue;
            if(W2&(1<<C.at(to))) dfs(dfs,to,W2,cost);
            else dfs(dfs,to,W2+(1<<C.at(to)),cost+W.at(C.at(to)));
        }
        visited.at(pos) = false;
    }; 
        dfs(dfs,u,1<<C.at(u),W.at(C.at(u)));
        cout << now << endl;
    }
}
0