結果
問題 | No.1690 Power Grid |
ユーザー |
|
提出日時 | 2021-09-24 21:26:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 161 ms / 3,000 ms |
コード長 | 1,916 bytes |
コンパイル時間 | 2,209 ms |
コンパイル使用メモリ | 200,412 KB |
最終ジャッジ日時 | 2025-01-24 16:46:35 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using ll = long long; using std::cin; using std::cout; using std::endl; std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count()); template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; } const int inf = (int)1e9 + 7; const long long INF = 1LL << 60; void solve([[maybe_unused]] int CASE) { int n, m, K; cin >> n >> m >> K; std::vector<ll> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } std::vector<std::vector<ll>> d(n, std::vector<ll>(n, INF)); for (int i = 0; i < m; ++i) { ll x, y, z; cin >> x >> y >> z; x -= 1, y -= 1; chmin(d[x][y], z); chmin(d[y][x], z); } for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { chmin(d[i][j], d[i][k] + d[k][j]); } } } std::vector<ll> dp(1 << n, INF); dp[0] = 0; for (int S = 0; S < (1 << n); ++S) { for (int i = 0; i < n; ++i) { if (S >> i & 1) continue; int nS = S | (1 << i); if (S == 0) { chmin(dp[nS], dp[S] + a[i]); } else { ll min = INF; for (int j = 0; j < n; ++j) { if (S >> j & 1) { chmin(min, d[j][i]); } } chmin(dp[nS], dp[S] + a[i] + min); } } } ll res = INF; for (int S = 0; S < (1 << n); ++S) { int cnt = 0; for (int i = 0; i < n; ++i) { if (S >> i & 1) cnt += 1; } if (cnt == K) chmin(res, dp[S]); } cout << res << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int kkt = 1; // cin >> kkt; for (int jupi = 1; jupi <= kkt; jupi++) solve(jupi); return 0; }