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

全源最短路 Johnson算法

image
image

洛谷p5905

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII;
const int N=3e3+10,INF=1e9;
vector<PII> edges[N];
int dist[N],n,m;
int cnt[N],h[N];
bool st[N];bool spfa(){memset(h,0x3f,sizeof(h));queue<int> q;q.push(0);st[0]=true;h[0]=0;while(q.size()){int u=q.front();q.pop();st[u]=false;for(auto &[v,w]:edges[u]){if(h[v]>h[u]+w){h[v]=h[u]+w;cnt[v]=cnt[u]+1;if(!st[v]){q.push(v);st[v]=true;}if(cnt[v]>=n+1)return false;}}}return true;
}void dijkstra(int s){for(int i=1;i<=n;i++){dist[i]=INF;}auto cmp=[](PII &x,PII &y){return x.second>y.second;};dist[s]=0;priority_queue<PII,vector<PII>,decltype(cmp)> heap(cmp);heap.push({s,0});while(heap.size()){int u=heap.top().first,d=heap.top().second;heap.pop();if(dist[u]<d)continue;for(auto &[v,w]:edges[u]){if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;heap.push({v,dist[v]});}}}
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;edges[u].push_back({v,w});}for(int i=1;i<=n;i++){edges[0].push_back({i,0});}if(!spfa()){cout<<-1<<endl;return 0;}for(int u=1;u<=n;u++){for(auto &[v,w]:edges[u]){w+=h[u]-h[v];}}for(int i=1;i<=n;i++){dijkstra(i);LL ans=0;for(int j=1;j<=n;j++){if(dist[j]==INF)ans+=1ll*j*INF;elseans+=1ll*j*(dist[j]+h[j]-h[i]);}cout<<ans<<endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=25565

相关文章:

  • 《对象创建的秘密:Java 内存布局、逃逸分析与 TLAB 优化详解》 - 实践
  • go get net/http connections count, using middleware
  • win11开机后卡死,磁盘c盘占用100%,解决方案
  • 跨越国度 解题报告
  • 手写Promise核心代码
  • 手动数据库分库分片策略
  • 大数据分析公司季度业绩与技术进展
  • tmux 终端复用器教程,创建一个持久的会话
  • 理解Transformer中的位置编码
  • 网络风险管理的三大关键洞察
  • 牛客 周赛110 20251007
  • Python列表初始化的陷阱:重复引用的坑
  • MongoDB
  • 实用指南:第三十三天打卡复习
  • 实用指南:Hardening fixes lead to hard questions
  • 赛前训练6 状压
  • 排序综合
  • NKOJ全TJ计划——NP11745
  • InfinityFree教程 ——免费搭建属于你的网站
  • 关于调和级数估算前n项的和
  • 10.6 模考 T4(QOJ 1836)
  • 实用指南:【Node.js 深度解析】npm install 遭遇:npm ERR! code CERT_HAS_EXPIRED 错误的终极解决方案
  • 顺序结构
  • Windows漏洞利用技巧:虚拟内存访问陷阱(2025更新)
  • Python编译期优化:隐藏在代码背后的效率魔法
  • 一篇文章带你了解 WGCLOUD运维监控系统的部署与应用
  • 选择结构
  • Python函数默认参数陷阱:可变对象的共享问题深度解析
  • 无需安装的Photoshop:网页版完整使用指南与在线图片编辑技巧
  • 求阶