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

河南网站建设公司谷歌搜索引擎优化seo

河南网站建设公司,谷歌搜索引擎优化seo,wordpress主题页添加,成都网站开发文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接:743. 网络延迟时间 相关链接: [图最短路模板] 五大最短路常用模板) 2. 题目解析 怎么讲呢,挺抽象的…很久没写最短路算法了。反正也是写出来了,但脱离了模板,把…

文章目录

    • 1. 题目来源
    • 2. 题目解析

1. 题目来源

链接:743. 网络延迟时间

相关链接:

  • [图+最短路+模板] 五大最短路常用模板)

2. 题目解析

怎么讲呢,挺抽象的…很久没写最短路算法了。反正也是写出来了,但脱离了模板,把自己还给绕进去了…

这块还是按照模板来写吧。

至于具体的算法思想,看相关链接即可。


  • 时间复杂度 O ( n m ) O(nm) O(nm)
  • 空间复杂度 O ( 1 ) O(1) O(1)

标准 spfa

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<pair<int, int>> g[n + 1];for (auto& e : times) {int x = e[0], y = e[1], w = e[2];g[x].push_back({y, w});}// 标准 spfa 算法queue<int> q; vector<int> dist(n + 1, 1e9);   // 注意这里初始化的是最大值vector<bool> st(n + 1, false);q.push(k);dist[k] = 0;while (q.size()) {auto x = q.front(); q.pop();st[x] = false; // x 不在队列中for (auto& [y, w] : g[x]) { // 更新 x 点临边if (dist[y] > dist[x] + w) { // 如果 y 点可以被 x 点更新dist[y] = dist[x] + w; // 则更新if (!st[y]) { // 如果 y 不在队列中,则加入q.push(y);st[y] = true;}}}}int res = -1e9;for (int i = 1; i <= n; i ++ ) {if (dist[i] == 1e9) return -1;  // 这里也是拿最大值进行的判断res = max(res, dist[i]);}return res;}
};

以下是 y 总写的 spfa 模板,大同小异。

const int N = 110, M = 6010, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];class Solution {
public:void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}void spfa(int start) {queue<int> q;q.push(start);memset(dist, 0x3f, sizeof dist);dist[start] = 0;while (q.size()) {int t = q.front();q.pop();st[t] = false;for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];if (!st[j]) {q.push(j);st[j] = true;}}}}}int networkDelayTime(vector<vector<int>>& times, int n, int k) {memset(h, -1, sizeof h);idx = 0;for (auto& e: times) {int a = e[0], b = e[1], c = e[2];add(a, b, c);}spfa(k);int res = 1;for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);if (res == INF) res = -1;return res;}
};作者:yxc
链接:https://www.acwing.com/activity/content/code/content/1011633/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

2024年11月26日00:08:57
这里不知道随便写的 spfa 也过了…
不要留下坏印象…

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<pair<int, int>>> g(n, vector<pair<int, int>>{});for (auto& e : times) {int x = e[0] - 1, y = e[1] - 1, w = e[2];g[x].push_back({y, w});}queue<int> q; vector<int> st(n, -1);  // 即是 st 又是 dist,用 -1 做状态标记位k = k - 1;q.push(k);st[k] = 0;while (q.size()) {auto x = q.front(); q.pop();for (auto& [y, w] : g[x]) {if (st[y] == -1 || st[y] > st[x] + w) { // 这里其实参考的是 dij 算法,又像 spfast[y] = st[x] + w;q.push(y);}}}int res = -1e9;for (int& x : st) {if (x == -1) return -1;res = max(res, x);}return res;}
};
http://www.zhongyajixie.com/news/17142.html

相关文章:

  • 链接测试对于网站的意义宁波seo在线优化
  • 网站模板插件惠州seo报价
  • 免费制作永久网站合作seo公司
  • 益阳建设网站公司淘宝店铺推广方式有哪些
  • 做日本外贸单是哪个网站在线生成网页网站
  • 白糖贸易怎么做网站网络视频营销平台
  • 红色网站主题腾讯企点账户中心
  • 网站上传小马后怎么做深圳信息公司做关键词
  • 建设网站的行业现状分析百度官网网站首页
  • 携程网站模板百度知道客服电话人工服务
  • 网站搭建报价表淘宝seo什么意思
  • 广州外贸营销型网站建设公司肇庆网站搜索排名
  • 软件网站建设基本流程图seo这个职位是干什么的
  • 做机械设备销售的那个网站好制作网页的代码
  • 如何选择丹阳网站建设seo网络营销的技术
  • 滴滴出行网站建设最新舆情信息网
  • 网站建设网络推广销售网站设计流程
  • e龙岩官网下载济南seo全网营销
  • 做网站的怎样找客户2345网址导航智能主板
  • 熊掌号网站改造绑定织梦网站国内真正的永久免费建站
  • 外贸网站怎么做效果好引擎搜索大全
  • 什么犁网站做淘宝门头域名查询 ip
  • 贵州省建设学校官方网站赚钱软件
  • 做网站需要哪些技术支持网络品牌营销
  • 网站建设公司企业文化广州seo全网营销
  • 延边州建设局网站百度一下百度首页官网
  • 博物馆网站建设策划书怎么在百度发广告
  • 烟台网站建设电话网络推广费用预算表
  • 门户 网站开发周期找营销推广团队
  • 网站界面设计基础深圳网站建设