Untitled
unknown
plain_text
a month ago
2.3 kB
2
Indexable
Never
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define AboTaha_on_da_code ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define X first #define Y second const int dx[8]={0, 0, 1, -1, 1, -1, -1, 1}, dy[8]={1, -1, 0, 0, 1, -1, 1, -1}; const int mod = 1e9+7; // 1e9+7, 998244353; const double EPS = 1e-8; int n, m, p; vector <int> sp; vector <ll> money; vector <vector <ll>> dp; vector <vector <ll>> adj; ll go(int cur = 0, int msk = 1) { if (msk == (1<<p)-1) return -adj[cur][0]; auto &ret = dp[cur][msk]; if (~ret) return ret; ret = -adj[cur][0]; for (int i = 0; i < p; i++) { if (!(msk>>i&1)) { ret = max(ret, money[i]-adj[cur][sp[i]]+go(sp[i], msk|(1<<i))); } } return ret; } void burn(int tc) { cin >> n >> m; n++; adj.assign(n, vector <ll> (n, 2e18)); for (int i = 0; i < n; i++) adj[i][i] = 0; while(m--) { int u, v; cin >> u >> v; string s; cin >> s; s.erase(s.begin()+s.find('.')); adj[u][v] = min(adj[u][v], stoll(s)); adj[v][u] = min(adj[v][u], adj[u][v]); adj[u][v] = min(adj[u][v], adj[v][u]); } for (int mi = 0; mi < n; mi++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { adj[i][j] = min(adj[i][j], adj[i][mi]+adj[mi][j]); } } } cin >> p; money.assign(n, 0); sp.clear(); sp.push_back(0); for (int i = 0; i < p; i++) { int u; cin >> u; string s; cin >> s; s.erase(s.begin()+s.find('.')); money[sp.size()]+=stoll(s); sp.push_back(u); } p++; dp.assign(n, vector <ll> ((1<<p), -1)); ll ans = go(); string rem = to_string(ans%100); if (ans%100 < 10) rem = "0"+rem; if (ans > 0) cout << "Daniel can save $" << ans/100 << '.' << rem; else cout << "Don't leave the house"; } int main() { AboTaha_on_da_code // freopen("zeros.in", "r", stdin); // freopen("Aout.txt", "w", stdout); int T = 1; cin >> T; for (int i = 1; i <= T; i++) { // cout << "Case " << i << ":\n"; // if (i > 1) cout << '\n'; burn(i); cout << '\n'; } return 0; }
Leave a Comment