383. 观光(最短路拓扑图)「建议收藏」

383. 观光(最短路拓扑图)「建议收藏」“您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。比荷卢经济联盟有很多公交线路。每天公共汽车都会从一座城市开往另一座城市。沿途汽车可能会在一些城市(零或更多)停靠。旅行社计划旅途从 S 城市出发,到 F 城市结束。由于不同旅客的景点偏好不同,所以为了迎合更多旅客,旅行社将为客户提供多种不同线路。游客可以选择的行进路线有所限制,要么满足所选路线总路程为 S 到 F 的最小路程,要么满足所选路线总路程仅比最小路程多一个单位长度。如上图所示,如果 S=1,F=5,则这里有两条最短路线 1→

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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

比荷卢经济联盟有很多公交线路。

每天公共汽车都会从一座城市开往另一座城市。

沿途汽车可能会在一些城市(零或更多)停靠。

旅行社计划旅途从 S 城市出发,到 F 城市结束。

由于不同旅客的景点偏好不同,所以为了迎合更多旅客,旅行社将为客户提供多种不同线路。

游客可以选择的行进路线有所限制,要么满足所选路线总路程为 S 到 F 的最小路程,要么满足所选路线总路程仅比最小路程多一个单位长度。

在这里插入图片描述

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

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

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

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

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

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

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

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

数据保证结果不超过 109。

数据范围
2≤N≤1000,
1≤M≤10000,
1≤L≤1000,
1≤A,B,S,F≤N

输入样例:
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
输出样例:
3
2

题解
最短路拓扑图

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
const int M = 2e4 + 10;
struct Ver{ 
   
    int id,type,dist;
    bool operator > ( const Ver &w)const{ 
   
        return dist > w.dist;
    }
};
int head[N],c;
struct Edge{ 
   
    int v,w,next;
}edge[M];
void add(int u,int v,int w){ 
   
    edge[c].v = v;
    edge[c].w = w;
    edge[c].next = head[u];
    head[u] = c ++;
}
int vis[N][2],dist[N][2],cnt[N][2];
int dijstra(int s,int e){ 
   
    priority_queue<Ver,vector<Ver>,greater<Ver> >q;
    memset(dist,INF,sizeof dist);
    memset(cnt,0,sizeof cnt);
    memset(vis,0,sizeof vis);
    dist[s][0] = 0;
    cnt[s][0] = 1;
    q.push({ 
   s,0,dist[s][0]});
    while(!q.empty()){ 
   
        Ver t = q.top();
        q.pop();
        int type = t.type,id = t.id,d = t.dist;
        if(vis[id][type])continue;
        vis[id][type] = true;
        for(int i = head[id];~i;i = edge[i].next){ 
   
            int v = edge[i].v,w = edge[i].w;
            if(dist[v][0] > d + w){ 
   
                dist[v][1] = dist[v][0],cnt[v][1] = cnt[v][0];
                dist[v][0] = d + w,cnt[v][0] = cnt[id][type];
                q.push({ 
   v,0,dist[v][0]});
                q.push({ 
   v,1,dist[v][1]});
            }
            else if(dist[v][0] == d + w)cnt[v][0] += cnt[id][type];
            else if(d + w < dist[v][1])dist[v][1] = d + w,cnt[v][1] = cnt[id][type],q.push({ 
   v,1,dist[v][1]});
            else if(d + w == dist[v][1])cnt[v][1] += cnt[id][type];
        }
    }
    if(dist[e][1] == dist[e][0] + 1)return cnt[e][1] + cnt[e][0];
    return cnt[e][0];
}
int main(){ 
   
    int T;
    cin>>T;
    while(T --){ 
   
        int n,m;
        int s,e;
        cin>>n>>m;
        int x,y,w;
        memset(head,-1,sizeof head);
        c = 0;
        for(int i = 0;i < m;i ++){ 
   
            cin>>x>>y>>w;
            add(x,y,w);
        }
        cin>>s>>e;
        cout<<dijstra(s,e)<<endl;
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169118.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 网站推荐:11个相似图片搜索网站(以图找图)

    网站推荐:11个相似图片搜索网站(以图找图)你想凭着一张现有图片找出它的原始图片,或者是凭着一张小的缩略图找出原始大图吗?下面的十款搜索引擎可以帮你实现,以图找图,以图搜图,以图片搜索相似的图片。一:http://tineye.com/Tineye是典型的以图找图搜索引擎,输入本地硬盘上的图片或者输入图片网址,即可自动帮你搜索相似图片,搜索准确度相对来说还比较令人满意。TinEye是加拿大Idée公司研发…

  • pycahrm激活码【在线破解激活】

    pycahrm激活码【在线破解激活】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • redis一级缓存和二级缓存_面试官让面试者先回去

    redis一级缓存和二级缓存_面试官让面试者先回去说起mybatis,大家可能都知道它是一个优秀的久层框架,它支持定制化SQL、存储过程以及高级映射。面试中都会问起mybatis一级缓存和二级缓存,它体现出你对mybatis这个开发中的理解,如果照着答案背的话只能拿到一个及格分,所以今天咱们就好好聊聊mybatis。另外本人整理了20年面试题大全,包含spring、并发、数据库、Redis、分布式、dubbo、JVM、微服务等方面总结,下图是部分截图,需要的话点这里点这里,暗号CSDN。1.首先,什么是Mybatis?MyBatis是一.

  • Mysql学习总结(10)——MySql触发器使用讲解

    Mysql学习总结(10)——MySql触发器使用讲解

  • 异步传输模式atm采用_ATM网是什么

    异步传输模式atm采用_ATM网是什么       异步传输模式(ATM)在ATM参考模式下构成一个协议集,用来建立一个在固定53比特流的数据包(信元)上运送所有通信流量的机制。固定大小的包可以确保迅速且容易地实现交换和多路技术功能。ATM是一种面向连接的技术,也就是说,两个网络系统要建立相互间的通信,应该通知所有的中间交换有关它们的服务需求和流量参数。  ATM参考模式分为三层:ATM适配层AAL、ATM层和物

  • idea中设置热部署

    idea中设置热部署首先我们再pom.xml中添加依赖和插件(下图两个红框)然后再进入idea左上角的file->setting,找到里面的compiler,把下图中红色的选项打钩,确定即可接下来要用到四个手指头了,依次按住Ctrl+Shift+Alt+/四个键,则会出现下面对话框,选中Registry然后出现下图,将compiler.automake.allow.when.app.running选项打钩然后把idea关掉再打开一下最后进去Chrome浏览器中,按F12,则出现下图,然后将下图中的

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号