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

计算最短路径的数量模板(最短路)

在这里插入图片描述

思路:计算最短路径的数量时,我们只需要在计算时dp即可,dp[i]代表走到i时的总路径

class Solution {
public:int countPaths(int n, vector<vector<int>>& edges) {vector<vector<tuple<int, long long, long long>>>ed(n);int c = 0;for(auto it : edges){ed[it[0]].push_back({it[1], it[2], c});ed[it[1]].push_back({it[0], it[2], c});c ++;}vector<long long>dis(n, 1000000000000000000), st(n);priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>q;q.push({0, 0});dis[0] = 0;vector<long long>dp(n);dp[0] = 1;//注意记住是怎么计算最短路径的个数的while(q.size()){auto [d, x] = q.top();q.pop();if(x == n - 1){return dp[n - 1] % 1000000007;}if(st[x]) continue;st[x] = 1;for(auto [u, v, i] : ed[x]){if(dis[u] > dis[x] + v){dis[u] = dis[x] + v;dp[u] = dp[x];q.push({dis[u], u});  }else if(dis[x] + v == dis[u])//相同的路径数量加一下{dp[u] = (dp[u] + dp[x]) % 1000000007;}}}return dp[n - 1];}
};
http://www.xdnf.cn/news/382249.html

相关文章:

  • 【智能指针】
  • 前端项目中单元测试与集成测试的管理实践
  • 基于51单片机的模拟洗衣机控制面板proteus仿真
  • JavaScript篇:async/await 错误处理指南:优雅捕获异常,告别失控的 Promise!
  • Java并发编程,从线程安全到死锁避免的实战解析
  • Java代码日志嵌入打包时间
  • 【排错】dify1.3.1插件市场安装报错问题
  • 《从零开始:构建你的第一个区块链应用》
  • 什么是文件描述符(File Descriptor,FD)
  • 45.中医知识问答管理员端对话信息查看功能bug修复(1)
  • 在 Vue 3 中实现刮刮乐抽奖
  • 进阶 DFS 学习笔记
  • 地学领域中常见的数据类型总结
  • 游戏服务器出现卡顿该怎么处理?
  • 学习黑客5 分钟深入浅出理解Linux Logs [特殊字符]
  • 【C++】string类
  • leetcode0829. 连续整数求和-hard
  • CountDownLatch 并发编程中的同步利器
  • JavaScript 内存管理与垃圾回收机制
  • DB4S:一个开源跨平台的SQLite数据库管理工具
  • BufferAttribute
  • vs查看dmp崩溃信息
  • Python递归函数
  • 【TypeScript】类型别名(Type Alias)与接口类型(Interface)
  • Redisson 看门狗机制
  • Unity3D仿星露谷物语开发41之创建池管理器
  • 记录一次window2012r2安装配置oracle11g的过程-出现的错误以及解决方法
  • 谷歌学术链接
  • OSPF综合应用
  • Nginx高级配置