結果
問題 | No.1690 Power Grid |
ユーザー |
|
提出日時 | 2021-09-24 21:49:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 3,000 ms |
コード長 | 2,696 bytes |
コンパイル時間 | 2,204 ms |
コンパイル使用メモリ | 199,296 KB |
最終ジャッジ日時 | 2025-01-24 17:06:20 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < n; i++) #define rep2(i, x, n) for (int i = x; i <= n; i++) #define rep3(i, x, n) for (int i = x; i >= n; i--) #define each(e, v) for (auto &e : v) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() using ll = long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; const int MOD = 1000000007; // const int MOD = 998244353; const int inf = (1 << 30) - 1; const ll INF = (1LL << 60) - 1; template <typename T> bool chmax(T &x, const T &y) { return (x < y) ? (x = y, true) : false; } template <typename T> bool chmin(T &x, const T &y) { return (x > y) ? (x = y, true) : false; } struct io_setup { io_setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; template <typename T, bool directed = false> struct Table { vector<vector<T>> es; const T INF_T = numeric_limits<T>::max() / 2; const int n; inline const vector<T> &operator[](int k) const { return es[k]; } inline vector<T> &operator[](int k) { return es[k]; } Table(int n) : es(n), n(n) { for (int i = 0; i < n; i++) es[i].assign(n, INF_T); for (int i = 0; i < n; i++) es[i][i] = 0; } void add_edge(int from, int to, T cost = 1) { es[from][to] = min(es[from][to], cost); if (!directed) es[to][from] = min(es[to][from], cost); } void warshall_floyd() { for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (es[i][k] == INF_T || es[k][j] == INF_T) continue; es[i][j] = min(es[i][j], es[i][k] + es[k][j]); } } } } }; int main() { int N, M, K; cin >> N >> M >> K; vector<ll> A(N); rep(i, N) cin >> A[i]; Table<ll> G(N); rep(i, M) { int u, v; ll c; cin >> u >> v >> c; u--, v--; G.add_edge(u, v, c); } G.warshall_floyd(); vector<ll> dp(1 << N, INF); dp[0] = 0; rep(i, 1 << N) { rep(j, N) { if ((i >> j) & 1) continue; ll x = INF; rep(k, N) { if ((i >> k) & 1) chmin(x, G.es[j][k]); } if (i == 0) x = 0; chmin(dp[i | (1 << j)], dp[i] + A[j] + x); } } ll ans = INF; rep(i, 1 << N) { if (__builtin_popcount(i) == K) chmin(ans, dp[i]); } cout << ans << '\n'; }