結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー |
![]() |
提出日時 | 2024-02-17 10:52:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 755 ms / 2,500 ms |
コード長 | 1,572 bytes |
コンパイル時間 | 1,246 ms |
コンパイル使用メモリ | 99,600 KB |
実行使用メモリ | 43,520 KB |
最終ジャッジ日時 | 2024-09-28 23:35:35 |
合計ジャッジ時間 | 11,485 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <iostream> #include <vector> using namespace std; struct DSU { vector<int> grp; DSU(int n = 0) : grp(n) { for (int i = 0; i < n; ++i) grp.at(i) = i; } int find(int u) { return grp.at(u) == u ? u : grp.at(u) = find(grp.at(u)); } void merge(int u, int v) { u = find(u); v = find(v); if (u != v) grp.at(v) = u; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector<pair<int, int>> edges(M); for (auto &[a, b] : edges) cin >> a >> b, --a, --b; vector<int> C(N); for (auto &c : C) cin >> c, --c; constexpr int D = 10; vector<long long> W(D); for (auto &w : W) cin >> w; vector<long long> Wsum(1 << D); for (int S = 0; S < (1 << D); ++S) { for (int i = 0; i < D; ++i) { if (S & (1 << i)) Wsum.at(S) += W.at(i); } } vector<DSU> dsus(1 << D); for (int S = 0; S < (1 << D); ++S) { dsus.at(S) = DSU(N); for (auto [a, b] : edges) { if ((S & 1 << C.at(a)) and (S & 1 << C.at(b))) dsus.at(S).merge(a, b); } } int Q; cin >> Q; constexpr long long inf = 1e18; while (Q--) { int u, v; cin >> u >> v; --u, --v; long long best = inf; for (int S = 0; S < (1 << D); ++S) { if (dsus.at(S).find(u) == dsus.at(S).find(v)) { best = min(best, Wsum.at(S)); } } if (best == inf) best = -1; cout << best << '\n'; } }