intfind(int u){ if (u == pa[u]) return u; return pa[u] = find(pa[u]); }
intmain(){ int n,m,S,T; cin >> n >> m >> S >> T; edges.resize(m); pa.resize(n + 1); for (int i = 0; i < m; ++i) { cin >> edges[i].u >> edges[i].v >> edges[i].a >> edges[i].b; as.insert(edges[i].a); }
sort(edges.begin(), edges.end(), cmp);
longlong ans = LLONG_MAX;
for (auto ca : as) { iota(pa.begin(), pa.end(), 0); int comps = n; int maxB = -1; for (auto e : edges) { if (e.a > ca) continue; int pu = find(e.u); int pv = find(e.v); if (pu != pv) { pa[pv] = pu; comps--; if (e.b > maxB) maxB = e.b; if (comps == 1) break; } }
if (comps == 1) { longlong cur = S * (longlong) ca + T * (longlong) maxB; if (cur < ans) ans = cur; } }
cout << ((ans == LLONG_MAX) ? -1 : ans);
return0; }
B. 这就是法国
传统题1000ms256MB
Description
众所周知，法国是一个经常罢工的国家。在20xx年，由于对工资过低且工作时间过长表示不满，工会决定在每个城市进行罢工要求政府提高福利待遇。法国政府决定派遣军队镇压罢工活动。已知法国有 n 座城市，第 i 座城市的坐标为 \((x_i, y_i)\)。法国军队要镇压所有城市罢工活动，法国可以空降军队到城市 i 镇压罢工，这样会伤亡 \(c_i\)。法国还可以派遣相邻的罢工活动已经镇压的城市 i 的军队到该城市 j；这样会伤亡 \((k_i + k_j) \times ((|x_i - x_j| + |y_i - y_j|)\)。军队可以在已经被镇压的城市间任意行动不会有任何伤亡。法国军队想要用最小的伤亡镇压所有罢工行为，请问最小伤亡人数有多少？
intmain(){ int n; cin >> n; vector<ll> x(n), y(n), c(n), k(n); for (int i = 0; i < n; i++) cin >> x[i] >> y[i]; for (int i = 0; i < n; i++) cin >> c[i]; for (int i = 0; i < n; i++) cin >> k[i];
auto dist = [&](int i, int j) -> ll { if (i == n && j < n) return c[j]; if (j == n && i < n) return c[i]; if (i == n && j == n) return0LL; return (k[i] + k[j]) * (std::llabs(x[i] - x[j]) + std::llabs(y[i] - y[j])); };
using Node = pair<ll, int>;
priority_queue<Node, vector<Node>, greater<Node>> pq; ll ans = 0;
for (int i = 0; i < n; i++) { key[i] = c[i]; pq.emplace(key[i],i); } key[n] = 0; pq.emplace(0,n);
while (!pq.empty()) { auto [cur, u] = pq.top(); pq.pop(); if (visited[u] || cur != key[u]) continue; visited[u] = true; ans += key[u];
for (int v = 0; v <= n; v++) { if (visited[v]) continue; ll curDist = dist(u, v); if (curDist < key[v]) { key[v] = curDist; pq.emplace(key[v], v); } } } cout << ans;
for (int i = 1; i <= n; i++) cin >> a[i]; int s = 1; for (int i = 2; i <= n; ++i) if (a[i] < a[s]) s = i;
for (int i = 1; i <= n; ++i) { if (i == s) continue; edges.push_back({s, i, a[i] + a[s]}); }
for (int i = 0; i < m; i++) { int u, v; ll cost; cin >> u >> v >> cost; edges.push_back({u, v, cost}); } sort(edges.begin(), edges.end(), cmp);
pa.resize(n+1); iota(pa.begin(), pa.end(),0);
ll ans = 0;
int comps = n; for (auto e : edges) { int pu = find(e.u), pv = find(e.v); if (pu != pv) { pa[pv] = pu; comps--; ans += e.cost; if (comps == 1) break; } } cout << ans;
intmain(){ int n,m; cin >> n >> m; vector<vector<Edge>> adj(n); while (m--) { int u,v,t,w; cin >> u >> v >> t >> w; u--; v--; adj[u].push_back({v,t, w}); adj[v].push_back({u,t, w}); }
