当前位置: 首页 > news >正文

最短路

经典图论

例题

P6833 [Cnoi2020] 雷雨

枚举三条路径交,求最小值即可。

最短路树

按松弛操作记录一个点的前驱,将前驱作为父亲建树。

性质

  • 形态不唯一
  • 根节点到其他所有点的最短距离与原图中相同
  • 在所有生成树中,最短路径树满足根节点到其他所有点的距离之和最短

例题

P5201 [USACO19JAN] Shortcut G

在最短路树上考虑问题,那么问题转化为求 \(\max \{ (dis_i - T) \times sz_i \}\)

题目要求最短路的字典序最小,在记录最短路前驱的时候顺便维护即可。

代码:

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;const int N = 1e4 + 5;
int n, m, t, u, v, w, ans, a[N], sz[N], fa[N], dis[N];
bool vis[N];
struct Node {int v, w;
} ;
vector<int> G[N];
vector<Node> g[N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;inline void dijkstra(int s) {fill(dis + 1, dis + 1 + n, 1e18);dis[s] = 0;q.push({0ll, s});while(! q.empty()) {auto [_, u] = q.top();q.pop();if(vis[u]) continue ;vis[u] = true;for(auto [x, w] : g[u]) {if(dis[u] + w < dis[x]) {fa[x] = u;dis[x] = dis[u] + w;q.push({dis[x], x});}else if(dis[u] + w == dis[x]) fa[x] = min(fa[x], u);}}return ;
}inline void dfs(int x, int last) {sz[x] = a[x];for(auto u : G[x])if(u != last) {dfs(u, x);sz[x] += sz[u];}ans = max(ans, (dis[x] - t) * sz[x]);return ;
}signed main() {ios_base :: sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m >> t;for(int i = 1 ; i <= n ; ++ i)cin >> a[i];    for(int i = 1 ; i <= m ; ++ i) {cin >> u >> v >> w;g[u].pb({v, w}), g[v].pb({u, w});}dijkstra(1);for(int i = 1 ; i <= n ; ++ i)G[i].pb(fa[i]), G[fa[i]].pb(i);dfs(1, -1);cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=33594

相关文章:

  • 2025年10月生成式引擎优化推荐对比:十家服务商资质、案例、售后全维度中立评价
  • 2025年10月生成式引擎优化推荐榜单:十强服务商多维对比与中立选购指南
  • 2025年10月远程控制软件推荐榜:节点小宝领衔的十强对比与中立评测
  • 2025年10月豆包排名优化推荐对比:聚焦资质、案例、售后的十家机构深度解读
  • 【何志丹】蹉跎半生,不知道是否能过45岁的坎
  • 2025年10月岩板岛台品牌推荐排名:聚焦高端定制需求与全案交付能力
  • 牛客小白月赛122 E
  • 深入解析:深度学习助力眼底疾病精准诊断:系统架构与设计思路解析
  • 2025年10月岩板工厂推荐评测榜:产能、专利、环保三维数据透视
  • PCIe扫盲——物理层电气部分基础(二)之De-emphasis
  • 2025年10月豆包关键词排名优化推荐对比榜:聚焦跨平台能力与售后体系的实用指南
  • PCIE 的 AFE DFE 是什么?
  • 2025年10月豆包关键词排名优化推荐榜:十强服务商多维对比与中立选购指南
  • 20232327 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 莫队学习笔记
  • 2025 年最新反应釜源头厂家排行榜:涵盖实验室 / 高压 / 加氢等类型设备,精选优质企业最新推荐
  • 2025年10月铝合金凉亭品牌推荐排行:深度评测五家主流厂商
  • PLAN(动态更新)
  • 2025 阻燃膜厂商最新推荐榜单:国际环保标准达标企业权威发布,覆盖 BOPET/PET/ 新能源专用全品类
  • 2025 年最新微波干燥设备生产厂家推荐排行榜:覆盖多行业需求,精选优质高效设备品牌指南黄粉虫微波/黑水虻微波/中药材微波干燥设备公司品牌推荐
  • 2025 年最新推荐钢结构源头厂家排行榜:聚焦美标 / 欧标钢结构等多领域,精选实力企业助力工程高效选材
  • 2025年10月访客系统推荐榜单详解:从核心指标到用户体验的客观剖析
  • 2025 年最新 1688 代运营公司排行榜:精选优质服务商,助力企业电商高效运营最新推荐
  • 2025年新明珠岩板深度解析:从智造规模到交付闭环的全景拆解
  • 2025 年北京红旗国悦 12 座 / 北京考斯特 4S 店 / 北京丰田柯斯达 / 北京考斯特商务车经销商推荐:大隆金马特装定制与全链条服务解析
  • 2025年10月deepseek关键词排名优化推荐评测榜:聚焦头部企业技术实力与服务透明度
  • AtCoder-abc228_h Histogram题解
  • 公钥私钥概念
  • 2025 年融合瓦生产厂家最新推荐排行榜:TPS/TPO/TPF 塑钢及钢塑一体融合瓦企业盘点与品质解析
  • 2025 年防腐瓦源头厂家最新推荐榜:聚焦塑钢防腐瓦 / PSP 塑钢覆合防腐瓦板等多类型产品,精选优质企业助力精准采购决策