結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー |
![]() |
提出日時 | 2024-02-16 23:46:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,500 ms |
コード長 | 3,209 bytes |
コンパイル時間 | 2,977 ms |
コンパイル使用メモリ | 259,696 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-09-28 22:50:49 |
合計ジャッジ時間 | 8,041 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>#include <algorithm>#include <vector>namespace nono {class UnionFind {public:UnionFind() = default;UnionFind(int size): size_(size), data_(size, -1) {}int leader(int x) {if (data_[x] < 0) {return x;} else {return data_[x] = leader(data_[x]);}}bool merge(int lhs, int rhs) {if (same(lhs, rhs)) {return false;}lhs = leader(lhs);rhs = leader(rhs);if (-data_[lhs] < -data_[rhs]) {std::swap(lhs, rhs);}data_[lhs] += data_[rhs];data_[rhs] = lhs;return true;}bool same(int lhs, int rhs) {return (leader(lhs) == leader(rhs));}int size(int x) {return -data_[leader(x)];}int size() const {return size_;}std::vector<std::vector<int>> groups() {std::vector<int> leader_buf(size_), group_size(size_);for (int i = 0; i < size_; i++) {leader_buf[i] = leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<int>> result(size_);for (int i = 0; i < size_; i++) {result[i].reserve(group_size[i]);}for (int i = 0; i < size_; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),result.end());return result;}private:int size_;std::vector<int> data_;};} // namespace nonovoid solve() {int n, m;std::cin >> n >> m;std::vector<std::pair<int, int>> edges;for (int i = 0; i < m; i++) {int u, v;std::cin >> u >> v;u--;v--;edges.emplace_back(u, v);}std::vector<int> c(n), w(10);for (int i = 0; i < n; i++) std::cin >> c[i];for (int i = 0; i < n; i++) c[i]--;for (int i = 0; i < 10; i++) std::cin >> w[i];int q;std::cin >> q;std::vector<std::pair<int, int>> query;for (int i = 0; i < q; i++) {int u, v;std::cin >> u >> v;u--;v--;query.emplace_back(u, v);}const long long INF = 1e18;std::vector<long long> ans(q, INF);for (int state = 0; state < (1 << 10); state++) {long long cost = 0;for (int i = 0; i < 10; i++) {if (state & (1 << i)) cost += w[i];}nono::UnionFind uf(n);for (auto [u, v]: edges) {if ((state & (1 << c[u])) && (state & (1 << c[v]))) {uf.merge(u, v);}}for (int i = 0; i < q; i++) {auto [u, v] = query[i];if ((state & (1 << c[u])) && (state & (1 << c[v])) && uf.same(u, v)) {ans[i] = std::min(ans[i], cost);}}}for (int i = 0; i < q; i++) {std::cout << (ans[i] == INF ? -1 : ans[i]) << '\n';}}int main() {std::cin.tie(0)->sync_with_stdio(0);std::cout << std::fixed << std::setprecision(16);int t = 1;while (t--) solve();}