博客
关于我
Codeforces Round #257 (Div. 1) B. Jzzhu and Cities(多条最短路)
阅读量:396 次
发布时间:2019-03-05

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

SPFA算法是一种用于计算图中单源最短路径的高效方法,特别适用于边权为非负数的图。在本次工程中,我们使用SPFA算法来解决一个与火车站相关的最短路径问题。

代码解析

#include 
using namespace std;typedef long long ll;const int maxn = 3e5 + 1;int n, m, k, u, v, w, x[maxn], y[maxn], cnt = 0;ll d[maxn], num[maxn];bool vis[maxn];vector
> g[maxn << 1);void spfa(int x) { memset(vis, false, sizeof(vis)); for (int i = 0; i <= n; ++i) { d[i] = 1e18; num[i] = 0; } d[x] = 0; num[x] = 1; queue
q; q.push(x); vis[x] = true; while (!q.empty()) { int top = q.front(); q.pop(); vis[top] = false; for (auto v : g[top]) { if (d[top] + v.second < d[v.first]) { d[v.first] = d[top] + v.second; num[v.first] = num[top]; if (!vis[v.first]) { q.push(v.first); vis[v.first] = true; } } else if (d[top] + v.second == d[v.first]) { num[v.first]++; } } }}int main() { scanf("%d %d %d", &n, &m, &k); for (int i = 1; i <= k; ++i) { scanf("%d", &u); scanf("%d", &v); scanf("%d", &w); g[u].push_back({v, w}); g[v].push_back({u, w}); scanf("%d", &x[i]); scanf("%d", &y[i]); g[1].push_back({x[i], y[i]}); g[x[i]].push_back({1, y[i]}); } spfa(1); if (d[x[i]] < y[i]) { cnt++; if (d[x[i]] == y[i] && num[x[i]] > 1) { cnt++; num[x[i]]--; } } printf("%d\n", cnt);}

代码解释

  • 数据结构初始化

    • g是一个邻接表,用于存储图的边信息。
    • d数组用于存储从源点到各个点的最短距离。
    • num数组用于记录到达各点的最短路径的次数。
    • vis数组用于标记当前点是否在队列中。
  • SPFA算法实现

    • 使用双端队列q进行广度优先搜索。
    • spfa函数初始化时,所有点的距离设为无穷大,源点距离设为0。
    • 将源点入队,并标记为已访问。
    • 每次从队列中取出点top,更新其邻接点的距离和计数器。
    • 如果发现更短的路径,更新距离和计数器,并将邻接点入队。
    • 如果发现与当前最短距离相等的路径,增加计数器。
  • 处理结果

    • 遍历所有火车站,比较实际计算的最短距离和预期距离。
    • 如果实际距离小于预期距离,计数器cnt加1。
    • 如果实际距离等于预期距离且有多条最短路径,计数器cnt再加1,并减少计数器以避免重复计数。
  • 通过SPFA算法,我们能够高效地计算出火车站到各个点的最短路径,并统计满足条件的最短路径数量。

    转载地址:http://rqewz.baihongyu.com/

    你可能感兴趣的文章
    npm错误 gyp错误 vs版本不对 msvs_version不兼容
    查看>>
    npm错误Error: Cannot find module ‘postcss-loader‘
    查看>>
    npm,yarn,cnpm 的区别
    查看>>
    NPOI
    查看>>
    NPOI之Excel——合并单元格、设置样式、输入公式
    查看>>
    NPOI初级教程
    查看>>
    NPOI利用多任务模式分批写入多个Excel
    查看>>
    NPOI在Excel中插入图片
    查看>>
    NPOI将某个程序段耗时插入Excel
    查看>>
    NPOI格式设置
    查看>>
    NPOI设置单元格格式
    查看>>
    Npp删除选中行的Macro录制方式
    查看>>
    NR,NF,FNR
    查看>>
    nrf24l01+arduino
    查看>>
    nrf开发笔记一开发软件
    查看>>
    nrm —— 快速切换 NPM 源 (附带测速功能)
    查看>>
    nrm报错 [ERR_INVALID_ARG_TYPE]
    查看>>
    NS3 IP首部校验和
    查看>>
    NSDateFormatter的替代方法
    查看>>
    NSError 的使用方法
    查看>>