[AcWing 1127] 香甜的黄油
2022/8/9 23:22:46
本文主要是介绍[AcWing 1127] 香甜的黄油,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
选一个起点,到其他点的最短距离之和最小
堆优化 dijkstra (太慢)
复杂度 \(O(n \cdot log(m) \cdot p) = 500 \times log(1450) \times 800 = 1.2 \times 10^7\)
点击查看代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int n, m, p; int id[N]; int h[N], e[N], ne[N], w[N], idx; int d[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++; } void dijkstra(int sp) { memset(d, 0x3f, sizeof d); memset(st, false, sizeof st); priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, sp}); d[sp] = 0; while (heap.size()) { auto t = heap.top(); heap.pop(); auto v = t.second; if (st[v]) continue; st[v] = true; for (int i = h[v]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] > d[v] + w[i]) { d[j] = d[v] + w[i]; heap.push({d[j], j}); } } } } void solve() { cin >> n >> p >> m; memset(h, -1, sizeof h); for (int i = 1; i <= n; i ++) cin >> id[i]; for (int i = 0; i < m; i ++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } int res = INF; for (int i = 1; i <= p; i ++) { dijkstra(i); int sum = 0; for (int j = 1; j <= n; j ++) { int dist = d[id[j]]; if (dist == INF) { sum = INF; break; } sum += dist; } res = min(res, sum); } cout << res << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }
- 堆优化 \(dijsktra\) 翻车,\(SPFA\) 活了过来
这篇关于[AcWing 1127] 香甜的黄油的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升