每周一算法:单源次短路

题目描述

“您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。

比荷卢经济联盟有很多公交线路。每天公共汽车都会从一座城市开往另一座城市。沿途汽车可能会在一些城市(零或更多)停靠。

旅行社计划旅途从 S S S 城市出发,到 F F F 城市结束。由于不同旅客的景点偏好不同,所以为了迎合更多旅客,旅行社将为客户提供多种不同线路。游客可以选择的行进路线有所限制,要么满足所选路线总路程为 S S S F F F 的最小路程,要么满足所选路线总路程仅比最小路程多一个单位长度。

在这里插入图片描述
如上图所示,如果 S = 1 S=1 S=1 F = 5 F=5 F=5,则这里有两条最短路线 1 → 2 → 5 , 1 → 3 → 5 1→2→5,1→3→5 125,135,长度为 6 6 6
;有一条比最短路程多一个单位长度的路线 1 → 3 → 4 → 5 1→3→4→5 1345,长度为 7 7 7

现在给定比荷卢经济联盟的公交路线图以及两个城市 S S S F F F,请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。

输入格式

第一行包含整数 T T T,表示共有 T T T 组测试数据。

每组数据第一行包含两个整数 N N N M M M,分别表示总城市数量和道路数量。

接下来 M M M 行,每行包含三个整数 A , B , L A,B,L A,B,L,表示有一条线路从城市 A A A 通往城市 B B B,长度为 L L L

需注意,线路是单向的,存在从 A A A B B B 的线路不代表一定存在从 B B B A A A 的线路,另外从城市 A A A 到城市 B B B 可能存在多个不同的线路。

接下来一行,包含两个整数 S S S F F F,数据保证 S S S F F F 不同,并且 S S S F F F 之间至少存在一条线路。

输出格式

每组数据输出一个结果,每个结果占一行。

数据保证结果不超过 1 0 9 10^9 109

样例 #1

样例输入 #1

2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1

样例输出 #1

3
2

提示

【数据范围】

2 ≤ N ≤ 1000 2≤N≤1000 2N1000,
1 ≤ M ≤ 10000 1≤M≤10000 1M10000,
1 ≤ L ≤ 1000 1≤L≤1000 1L1000
1 ≤ A , B , S , F ≤ N 1≤A,B,S,F≤N 1A,B,S,FN

算法思想

根据题目描述,求的是从 S S S 城市出发、到 F F F 城市结束的所有路线中,最短路、或者仅比最小路程多 1 1 1个单位长度的次短路的方案数。

在博主的另一篇文章每周一算法:最短路计数介绍过,可以使用动态规划的思想,定义状态 f [ i ] f[i] f[i]表示起点到顶点 i i i的最短路的方案数。为了能同时求出次短路的方案数,可以采用拆点的思想:

  • f [ i ] [ 0 ] f[i][0] f[i][0]表示起点到顶点 i i i的最短路的方案数
  • f [ i ] [ 1 ] f[i][1] f[i][1]表示起点到顶点 i i i的次短路的方案数

与最短路计数一样,图中有可能存在环,不一定存在拓扑序列,因此不能通过循环迭代直接计算状态;可以使用最短路算法,在计算最短路的同时将状态计算出来。同时,在计算最短路时,能够找到一个拓扑序来计算状态。这样就需要最短路算法能够构造出一个最短路拓扑图,如下图所示:
在这里插入图片描述
由于边权不相同,这里可以用Dijkstra算法求最短路。Dijkstra算法计算最短路时,每个点只会出队 1 1 1次,当一个点出队时,是不会更新前面已经出队的点到起点的最短路,因此出队序列满足拓扑序。

算法流程

  • 将起点 S S S的最短路初始化为 0 0 0,即 d i s [ S ] [ 0 ] = 0 dis[S][0]=0 dis[S][0]=0;方案数初始化为 1 1 1,即 f [ S ] [ 0 ] = 1 f[S][0] = 1 f[S][0]=1
  • 在求解最短路的过程中
    • v v v点到起点的最短路能够被点松弛:
      • 将之前的最短路变为次短路,更新次短路的方案数
      • 更新最短路的长度,设置最短路的方案数
    • v v v点到起点的最短路等于经过 u u u点中转的距离,累加最短路的方案数
    • v v v点到起点的次短路能够被点松弛:
      • 更新次短路的长度,设置次短路的方案数
    • v v v点到起点的次短路等于经过 u u u点中转的距离,累加次短路的方案数
  • 最后,如果次短路的长度 + 1 +1 +1等于最短路长度,即 d i s [ F ] [ 1 ] = d i s [ F ] [ 0 ] + 1 dis[F][1] = dis[F][0] + 1 dis[F][1]=dis[F][0]+1,那么总方案数为 f [ F ] [ 0 ] + f [ F ] [ 1 ] f[F][0]+f[F][1] f[F][0]+f[F][1];否则,总方案数为 f [ F ] [ 0 ] f[F][0] f[F][0]

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 1e4 + 5;
int h[N], e[M], w[M], ne[M], idx; 
int n, m, S, F;
int dis[N][2], f[N][2]; //f[i][0]表示到i点最短路条数
bool st[N][2];
struct V {
    int ver, type, dis; //节点、类型(0最短路、1次短路)、到起点距离
    bool operator > (const V &v) const //小顶堆,重载 > 
    {
        return dis > v.dis;
    }
};
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra()
{
    memset(st, 0, sizeof st);
    memset(dis, 0x3f, sizeof dis);
    memset(f, 0, sizeof f);
    dis[S][0] = 0, f[S][0] = 1; //初始化最短路和条数
    priority_queue<V, vector<V>, greater<V>> q; //小顶堆
    q.push({S, 0, 0}); //起点最短路入堆
    while(q.size())
    {
        V t = q.top(); q.pop();
        int u = t.ver, type = t.type, d = t.dis, cnt = f[u][type];
        if(st[u][type]) continue;
        st[u][type] = true;
        
        for(int i = h[u]; ~ i; i = ne[i])
        {
            int v = e[i];
            if(dis[v][0] > d + w[i]) //可以更新最短路
            {
                dis[v][1] = dis[v][0], f[v][1] = f[v][0]; //最短路变次短路,同时更新次短路个数
                q.push({v, 1, dis[v][1]}); //次短路入堆
                dis[v][0] = d + w[i], f[v][0] = cnt; //更新最短路以及最短路个数
                q.push({v, 0, dis[v][0]});
            }
            else if(dis[v][0] == d + w[i]) //与最短路相等
            {
                f[v][0] += cnt; //累加最短路个数
            }
            else if(dis[v][1] > d + w[i]) //可以更新次短路
            {
                dis[v][1] = d + w[i], f[v][1] = cnt;
                q.push({v, 1, dis[v][1]});
            }
            else if(dis[v][1] == d + w[i]) //与次短路相等
            {
                f[v][1] += cnt;
            }
        }
    }
    int ans = f[F][0]; //最短路个数
    if(dis[F][1] == dis[F][0] + 1) //次短路等于最短路+1
        ans += f[F][1];
    return ans;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T --)
    {
        scanf("%d%d", &n, &m);
        memset(h, -1, sizeof h);
        idx = 0;
        while(m --)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d%d", &S, &F);
        printf("%d\n", dijkstra());
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/583457.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

新书速览|ChatGLM3大模型本地化部署、应用开发与微调

实战文本生成、智能问答、信息抽取、财务预警应用开发&#xff0c;掌握ChatGLM3大模型部署、开发与微调技术 01 本书内容 《ChatGLM3大模型本地化部署、应用开发与微调》作为《PyTorch 2.0深度学习从零开始学》的姊妹篇&#xff0c;专注于大模型的本地化部署、应用开发以及微…

挤压激励注意力 SE | Squeeze-and-Excitation Networks

论文名称&#xff1a;《Squeeze-and-Excitation Networks》 论文地址&#xff1a;https://arxiv.org/pdf/1709.01507.pdf 代码地址&#xff1a; https://github.com/hujie-frank/SENet 卷积神经网络 (CNN) 的核心构建块是卷积运算符&#xff0c;它使网络能够通过在每一层的局…

C++ | Leetcode C++题解之第50题Pow(x,n)

题目&#xff1a; 题解&#xff1a; class Solution { public:double quickMul(double x, long long N) {if (N 0) {return 1.0;}double y quickMul(x, N / 2);return N % 2 0 ? y * y : y * y * x;}double myPow(double x, int n) {long long N n;return N > 0 ? qu…

谷歌CEO谈拥有“最好的”AI、1000 种新云产品和Workspace

谷歌首席执行官桑达尔皮查伊 (Sundar Pichai) 在谷歌财报中发表了大胆言论&#xff0c;其中包括将 Workspace 吹捧为网络安全领域的领导者、谷歌云和 YouTube 到今年年底的总运行额将达到 1000 亿美元&#xff0c;以及为什么需要“强大的合作伙伴计划”来推动人工智能发展。 谷…

70、栈-最小栈

思路&#xff1a; 除了最后一个获取最小值以外&#xff0c;其他都可以使用一个栈来实现&#xff0c;但是如果当前一个最小值被移除了&#xff0c;如果获取第二小的值&#xff0c;这个是需要记录的。所以最好的办法是两个栈。一个作为主栈存放数据&#xff0c;一个作为辅栈&…

C++之类和对象

目录 一&#xff1a;再谈构造函数 1.1 构造函数体赋值 1.2 初始化列表 1.3 explicit关键字 二. static成员 2.2 特性 三. 友元 3.1 友元函数 3.2 友元类 四&#xff1a; 内部类 五&#xff1a;匿名对象 六. 再次理解类和对象 一&#xff1a;再谈构造函数 1.1 构造…

关于discuz论坛网址优化的一些记录(网站地图sitemap提交)

最近网站刚上线&#xff0c;针对SEO做了些操作&#xff0c;为了方便网站网页百度被收录&#xff0c;特此记录下 discuz有免费的sitemap插件可以用&#xff0c;打开后台管理&#xff0c;找到插件栏&#xff0c;然后找到更多插件&#xff0c;进入插件市场。 选择这个免费的sitem…

ios CI/CD 持续集成 组件化专题四-(手动发布私有库-组件化搭建)

一 、创建私有索引库 1.1 、第一步 首先检查本地是否存在需要的私有索引库 pod repo list 例如&#xff1a;dp_base_ios_spec 在本地不存在该私有索引库 1.2 、第二步 在git下下创建一个新的库&#xff0c;这个库用来保存私有库的podspec文件&#xff0c;取名叫xxxSpec用以…

计算机组成实验(5)

一、实验目的和要求 1.1 实验目的 1. 复习二进制加减、乘除的基本法则 2. 掌握补码的基本原理和作用 3. 了解浮点数的表示方法及加法运算法则 4. 进一步了解计算机系统的复杂运算操作 1.2 实验要求 1. 熟悉二进制原码补码的概念,了解二进制加减乘除的原理与操作实现。 …

力扣HOT100 - 207. 课程表

解题思路&#xff1a; class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] inDegree new int[numCourses];//存每个结点的入度List<List<Integer>> res new ArrayList<>();//存结点之间依赖关系Queue<Integer>…

buuctf——web题目练习

1.极客大挑战2019 easysql 密码或者用户输入万能密码即可 关于万能密码的理解和原理&#xff0c;可以参考这篇BUUCTF[极客大挑战 2019] EasySQL 1_[极客大挑战 2019]easysql 1-CSDN博客 2.极客大挑战2019 have fun 题目源码 需要构造payload 网页传参可参考&#xff1a;…

设计模式 基本认识

文章目录 设计模式的作用设计模式三原则设计模式与类图设计模式的分类 设计模式的作用 设计模式是在软件设计过程中针对常见问题的解决方案的一种通用、可重用的解决方案。设计模式提供了一种经过验证的方法&#xff0c;可以帮助开发人员解决特定类型的问题&#xff0c;并在软…

C++常用的输入输出方法(ACM模式)

文章目录 前言一、输入输出方法1、cin2、getline()3、getchar() 二、算法案例1、一维数组1.1 输入固定长度1.2长度不固定 2、固定二维数组3、以非空格隔开的元素输入3、常见数据结构定义以及输入3.1 链表 前言 C中的输入输出函数有很多&#xff0c;我们本章只针对大部分算法题…

Makefile 快速入门

参考自:Makefile 20分钟入门&#xff0c;简简单单&#xff0c;展示如何使用Makefile管理和编译C代码_哔哩哔哩_bilibili 注: 视频中用的是C&#xff0c;博主这里用C语言实现 喜欢老师的于老师的还请多多点赞&#xff0c;觉得博主写得不错的&#xff0c;也可以点赞、收藏哦 本…

mars3d实现获取线上不同历里程的坐标

mars3d实现获取线上不同历里程的坐标应用效果 线路数据是这样的&#xff0c;由很多段组成的&#xff0c;是不是就只能一段一段去计算看处于哪一段上具体位置 相关说明&#xff1a;想要实现以上效果的话&#xff0c;mars3d实现需要以下两点 1、需要合并线 2、可以利用 http://m…

学习周报:文献阅读+Fluent案例+有限体积法理论学习

目录 摘要 Abstract 文献阅读&#xff1a;基于物理信息神经网络的稀疏数据油藏模拟 文献摘要 文章讨论|结论 各方程和原理简介 PINN简介 域分解 实验设置 单相油藏问题 油水两相问题 Fluent实例&#xff1a;Y型弯管中的流体混合分析 几何建模部分 网格划分 求解器设…

贝叶斯统计实战:Python引领的现代数据分析之旅

贝叶斯统计这个名字取自长老会牧师兼业余数学家托马斯贝叶斯(Thomas Bayes&#xff0c;1702—1761)&#xff0c;他最先推导出了贝叶斯定理&#xff0c;该定理于其逝世后的1763年发表。但真正开发贝叶斯方法的第一人是Pierre-Simon Laplace(1749—1827)&#xff0c;因此将其称为…

C++|STL-list运用(1)

cplusplus.com/reference/list/list/?kwlist list介绍 list是一个双向循环链表&#xff0c;双向循环链表它的每个节点都有两个链接&#xff0c;一个指向前一个节点&#xff0c;另一个指向下一个节点&#xff0c;且最后一个结点指向头节点。 结点组成 1.数据域 2.指针域 &a…

多校园版 校园跑腿小程序源码系统 跑腿达人自主入住接单 带完整的安装代码包以及部署教程

近年来&#xff0c;随着移动互联网的普及和高校信息化的推进&#xff0c;校园跑腿服务逐渐成为了校园内的一种新兴业态。然而&#xff0c;市场上的校园跑腿小程序大多功能单一、缺乏个性化定制&#xff0c;难以满足不同高校、不同用户的需求。因此&#xff0c;小编给大家分享一…

Java:SpringBoot如何优化启动速度

一、yml中设置懒加载 spring:main:lazy-initialization: true 二、SpringBoot启动类中添加注解 Indexed &#xff08;Spring5才有该注解&#xff09; Indexed EnableAsync RestController SpringBootApplication(exclude {WxMaAutoConfiguration.class}) EnableTransactionM…