結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー |
|
提出日時 | 2024-02-16 23:10:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 248 ms / 2,500 ms |
コード長 | 2,493 bytes |
コンパイル時間 | 935 ms |
コンパイル使用メモリ | 96,824 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-28 21:46:25 |
合計ジャッジ時間 | 5,276 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <iostream> #include <vector> using namespace std; using ll = long long; constexpr ll INF = 1000000000000000000LL; class UnionFind { private: int N; vector<int> par, size; public: UnionFind (int N_) { reset(N_); } void reset (int N_) { N = N_; par.resize(N); size.resize(N); for (int i = 0; i < N; i++) { par[i] = i; size[i] = 1; } } int root (int u) { if (par[u] == u) return u; return par[u] = root(par[u]); } bool same (int u, int v) { return root(u) == root(v); } bool unite (int u, int v) { u = root(u); v = root(v); if (u == v) return false; int l = u, s = v; if (size[u] < size[v]) swap(l, s); par[s] = par[l]; size[l] += size[s]; return true; } }; int main () { int N, M; cin >> N >> M; vector<pair<int, int>> edges(M); for (int i = 0; i < M; i++) { int A, B; cin >> A >> B; A--, B--; edges[i] = make_pair(A, B); } vector<int> C(N); for (int i = 0; i < N; i++) cin >> C[i]; for (int i = 0; i < N; i++) C[i]--; vector<int> W(10); for (int i = 0; i < 10; i++) cin >> W[i]; int Q; cin >> Q; vector<ll> ans(Q); vector<pair<int, int>> query(Q); for (int i = 0; i < Q; i++) { int u, v; cin >> u >> v; u--, v--; query[i] = make_pair(u, v); ans[i] = INF; } // UF全通り UnionFind UF(N); for (int bit = 0; bit < (1<<10); bit++) { UF.reset(N); ll cost = 0; for (int i = 0; i < 10; i++) if ( 0 < (bit & (1<<i)) ) cost += W[i]; for (int i = 0; i < M; i++) { int u = edges[i].first; int v = edges[i].second; if ( (bit & (1<<C[u])) == 0 ) continue; if ( (bit & (1<<C[v])) == 0 ) continue; UF.unite(u, v); } for (int i = 0; i < Q; i++) { int u = query[i].first; int v = query[i].second; if (!UF.same(u, v)) continue; ans[i] = min(ans[i], cost); } } // 出力 for (int i = 0; i < Q; i++) { if (ans[i] == INF) { cout << "-1\n"; } else { cout << ans[i] << "\n"; } } }