当前位置:网站首页>洛谷 P1629 邮递员送信 (三种最短路)
洛谷 P1629 邮递员送信 (三种最短路)
2022-08-10 19:07:00 【eyuhaobanga】
题意容易理解,从1出发到其他所有点并返回的最短路,需要先正着跑一边,然后建反边再跑一边
Dijkstra:
#include <bits/stdc++.h> #define rep(i,a,n) for(int i=a;i<n;i++) using namespace std; using LL = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<pair<int, int>>> G(n + 1), G1(n + 1); vector<int> dist(n + 1, 0x3f3f3f3f), dist1(n + 1, 0x3f3f3f3f); rep (i, 0, m) { int u, v, c; cin >> u >> v >> c; G[u].push_back(make_pair(v, c)); G1[v].push_back(make_pair(u, c)); } LL ans = 0; dist[1] = 0; set<pair<int, int>> se, se1; for (int i = 1; i <= n; i++) { se.insert(make_pair(dist[i], i)); } while (!se.empty()) { int u = se.begin()->second; se.erase(se.begin()); if (dist[u] > 1 << 30) { break; } for (auto v : G[u]) { if (dist[u] + v.second < dist[v.first]) { se.erase(make_pair(dist[v.first], v.first)); dist[v.first] = dist[u] + v.second; se.insert(make_pair(dist[v.first], v.first)); } } } for (int i = 1; i <= n; i++) { ans += dist[i]; } dist1[1] = 0; for (int i = 1; i <= n; i++) { se1.insert(make_pair(dist1[i], i)); } while (!se1.empty()) { int u = se1.begin()->second; se1.erase(se1.begin()); if (dist1[u] > 1 << 30) { break; } for (auto v : G1[u]) { if (dist1[u] + v.second < dist1[v.first]) { se1.erase(make_pair(dist1[v.first], v.first)); dist1[v.first] = v.second + dist1[u]; se1.insert(make_pair(dist1[v.first], v.first)); } } } for (int i = 1; i <= n; i++) { ans += dist1[i]; } cout << ans << '\n'; return 0; }
bellman ford:
#include <bits/stdc++.h> #define rep(i,a,n) for(int i=a;i<n;i++) using namespace std; using LL = long long; struct Edge { int x, y, v; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<Edge> G(m + 1), G1(m + 1); for (int i = 1; i <= m; i++) { int u, v, c; cin >> u >> v >> c; G[i].x = u; G[i].y = v; G[i].v = c; G1[i].x = v; G1[i].y = u; G1[i].v = c; } vector<int> dist(n + 1, 0x3f3f3f3f); dist[1] = 0; while (true) { bool ok = false; for (int i = 1; i <= m; i++) { int x = G[i].x, y = G[i].y, w = G[i].v; if (dist[x] < 1 << 30) { if (dist[x] + w < dist[y]) { dist[y] = dist[x] + w; ok = true; } } } if (!ok) { break; } } vector<int> dist1(n + 1, 0x3f3f3f3f); dist1[1] = 0; while (true) { bool ok = false; for (int i = 1; i <= m; i++) { int x = G1[i].x, y = G1[i].y, w = G1[i].v; if (dist1[x] < 1 << 30) { if (dist1[x] + w < dist1[y]) { dist1[y] = w + dist1[x]; ok = true; } } } if (!ok) { break; } } LL ans = 0; for (int i = 2; i <= n; i++) { ans += dist1[i] + dist[i]; } cout << ans << '\n'; return 0; }
floyd (n>=1000慎用,该题吸氧可过):
#include <bits/stdc++.h> #define rep(i,a,n) for(int i=a;i<n;i++) using namespace std; using LL = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> a(n + 1, vector<int> (n + 1, 0x3f3f3f3f)); rep (i, 0, m) { int u, v, c; cin >> u >> v >> c; a[u][v] = min(a[u][v], c); } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = min(a[i][j], a[i][k] + a[k][j]); } } } LL ans = 0; for (int i = 2; i <= n; i++) { ans = ans + a[1][i] + a[i][1]; } cout << ans << '\n'; return 0; }
关于spfa,它已经死了,请不要在任何公共场合写spfa
边栏推荐
- 转铁蛋白(Tf)修饰去氢骆驼蓬碱磁纳米脂质体/香豆素-6脂质体/多柔比星脂质体
- 杭电多校七 1003-Counting Stickmen(组合数学)
- Common ports and services
- 陕西CAS:1244028-50-9_Biotin-PEG3-SCO-PPh3 固体
- Linux服务器安装Redis,详细步骤。
- CAS:2055042-70-9_N-(叠氮基-PEG4)-生物素
- [Go WebSocket] Your first Go WebSocket server: echo server
- 手把手教你Charles抓包工具使用
- 网络虚拟化
- QoS Quality of Service Seven Switch Congestion Management
猜你喜欢
主动信息收集
子域名收集&Google搜索引擎语法
We used 48h to co-create a web game: Dice Crush, to participate in international competitions
【C#】WCF和TCP消息通信练习,实现群聊功能
Solution for thread not gc-safe when Rider debugs ASP.NET Core
魔方电池如何“躺赢”?解锁荣威iMAX8 EV“头等舱”安全密码
力扣18-四数之和——双指针法
[Teach you how to make a small game] Write a function with only a few lines of native JS to play sound effects, play BGM, and switch BGM
MATLAB设计,FPGA实现,联合ISE和Modelsim仿真的FIR滤波器设计
spark学习笔记(九)——sparkSQL核心编程-DataFrame/DataSet/DF、DS、RDD三者之间的转换关系
随机推荐
这7个自动化办公模版 教你玩转表格数据自动化
含有PEG 间隔基和一个末端伯胺基团(CAS:1006592-62-6)化学试剂
子域名收集&Google搜索引擎语法
keepalived:故障检测自动修复脚本
哈工大软件构造Lab3(2022)
血红素-金纳米颗粒(Heme-AuNP)复合纳米酶|金纳米颗粒核多孔空心碳纳米球壳([email protected])纳米酶
机器学习|模型评估——AUC
QoS服务质量七交换机拥塞管理
【毕业设计】基于Stm32的智能疫情防控门禁系统 - 单片机 嵌入式 物联网
mysql----group by、where以及聚合函数需要注意事项
常见端口及服务
【CNN】刷SOTA的trick
GBASE 8s 高可用RSS集群搭建
Hangdian Multi-School Seven 1003-Counting Stickmen (Combination Mathematics)
ARouter使用自定义注解处理器,自动生成跳转Activity的代码,避免手动填写和管理path
转铁蛋白Tf功能化β-榄香烯-雷公藤红素/紫杉醇PLGA纳米粒/雷公藤甲素脂质体(化学试剂)
Colocate Join :ClickHouse的一种高性能分布式join查询模型
[Teach you how to do mini-games] How to lay out the hands of Dou Dizhu?See what the UP master of the 250,000 fan game area has to say
测试/开发程序员值这么多钱么?“我“不会愿赌服输......
回老家去?