博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
挑战程序设计竞赛(第2版)第112页勘误
阅读量:6602 次
发布时间:2019-06-24

本文共 870 字,大约阅读时间需要 2 分钟。

整个代码段改为

// 输入

int N, ML, MD;int AL[MAX_ML], BL[MAX_ML], DL[MAX_ML];int AD[MAX_MD], BD[MAX_MD], DD[MAX_MD];int d[MAX_N]; //最短距离bool updated; // 是否有更新void update(int& x, int y) {if (x > y) {x = y;updated = true;}}// 用Bellman-Ford算法计算dvoid bellmanford() {for (int k = 0; k <= N; k++) {updated = false;// 从i+1到i的权值为0for (int i = 0; i + 1 < N; i++) {if (d[i + 1] < INF) update(d[i], d[i + 1]);}// 从AL到BL的权值为DLfor (int i = 0; i < ML; i++) {if (d[AL[i] - 1] < INF) update(d[BL[i] - 1], d[AL[i] - 1] + DL[i]);}// 从BD到AD的权值为-DDfor (int i = 0; i < MD; i++) {if (d[BD[i] - 1] < INF) update(d[AD[i] - 1], d[BD[i] - 1] - DD[i]);}}}void solve() {// 检查是否存在负圈fill(d, d + N, 0);bellmanford();if (updated) {printf("-1\n");return;}fill(d, d + N, INF);d[0] = 0;bellmanford();int res = d[N - 1];if (res == INF) res = -2;printf("%d\n", res);}

转载于:https://www.cnblogs.com/orion7/p/8365666.html

你可能感兴趣的文章
xtrabackup备份还原
查看>>
HTML5 FileAPI
查看>>
使用tdcss.js轻松制作自己的style guide
查看>>
发布《iBoard 电子学堂》DEMO代码
查看>>
SecureCRTPortable.exe 如何上传文件
查看>>
什么是SysWow64
查看>>
C++中public、protected及private用法
查看>>
苹果公司的产品已用完后门与微软垄断,要检查起来,打架!
查看>>
chrome调试ajax
查看>>
centos 升级php、mysql(webtatic)
查看>>
Java并发编程:Lock
查看>>
oracle服务器和客户端字符集的查看和修改
查看>>
顶级的JavaScript框架、库、工具及其使用
查看>>
AYUI -AYUI风格的 超美 百度网盘8.0
查看>>
linux下php中文UTF-8转换Unicode方法和注意事项
查看>>
TensorFlow:tf.contrib.layers.xavier_initializer
查看>>
简明 Python 教程
查看>>
Photoshop操作指南
查看>>
用MPMoviePlayerController做在线音乐播放
查看>>
ASP.NET调用cmd命令提示符拒绝访问解决方案
查看>>