首页 > 其他分享 >分层图求最短路

分层图求最短路

时间:2024-11-04 19:42:22浏览次数:2  
标签:pq int 短路 leq 分层 pair 图求 make dis

分层图求最短路

速度限制

题目描述

在这个繁忙的社会中,我们往往不再去选择最短的道路,而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是,有一些限速的标志丢失了,因此你无法得知应该开多快。一种可以辩解的解决方案是,按照原来的速度行驶。你的任务是计算两地间的最快路线。

你将获得一份现代化城市的道路交通信息。为了使问题简化,地图只包括路口和道路。每条道路是有向的,只连接了两条道路,并且最多只有一块限速标志,位于路的起点。两地 $A$ 和 $B$,最多只有一条道路从 $A$ 连接到 $B$。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然,你的车速不能超过当前的速度限制。

输入格式

第一行是 $3$ 个整数 $N$,$M$ 和 $D$($2\leq N\leq 150$,$1\leq M\leq 22500$),表示道路的数目,用 $0 \sim N-1$ 标记。$M$ 是道路的总数,$D$ 表示你的目的地。

接下来的 $M$ 行,每行描述一条道路,每行有 $4$ 个整数 $A$($0\leq A<N$),$B$($0\leq B<N$),$V$ ($0\leq V\leq 500$)和 $L$($1\leq L\leq 500$),这条路是从 $A$ 到 $B$ 的,速度限制是 $V$,长度为 $L$。如果 $V$ 是 $0$,表示这条路的限速未知。

如果 $V$ 不为 $0$,则经过该路的时间 $T=\frac{L}{V}$。否则 $T=\frac{L}{\text{Vold}}$,$\text{Vold}$ 是你到达该路口前的速度。开始时你位于 $0$ 点,并且速度为 $70$。

输出格式

输出文件仅一行整数,表示从 $0$ 到 $D$ 经过的城市。

输出的顺序必须按照你经过这些城市的顺序,以 $0$ 开始,以 $D$ 结束。仅有一条最快路线。

样例 #1

样例输入 #1

6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40

样例输出 #1

0 5 2 3 1

考虑分层图。

建数组$dis[i][j]$表示从出发点到$i$点,速度为$j。vis[i][j]$表示从出发点到$i$,速度为$j$是否访问过。

为得到最短的路线,可以建一个$from[i][j]$数组,表示从出发点到$i$,速度为$j$的最短路的上一个点。最后跑一遍堆优化的$dijkstra$即可。

#include<bits/stdc++.h>
using namespace std;
const int N=160,M=510;
struct Node{
    int to,v;
    double l;
    Node(int to=0,int v=0,double l=0):to(to),v(v),l(l) {}
};
int n,m,t;
double dis[N][M];
pair<int,int> lst[N][M];
int vis[N][M];
vector<Node> g[N];
vector<int> ans;
void bfs(){		//dijkstra
    for(int i=1;i<=n;i++){
        for(int j=1;j<=M;j++) dis[i][j]=2e9;
    }
    dis[1][70]=0;
    priority_queue<pair<double,pair<int,int> > > pq;
    pq.emplace(0,make_pair(1,70));
    while(!pq.empty()){
        int u=pq.top().second.first;
        int o=pq.top().second.second;
        pq.pop();
        if(vis[u][o]) continue;
        vis[u][o]=1;
        for(auto v:g[u]){
            if(v.v&&dis[v.to][v.v]>dis[u][o]+v.l/v.v){		//有速度限制
                dis[v.to][v.v]=dis[u][o]+v.l/v.v;
                lst[v.to][v.v]=make_pair(u,o);
                pq.emplace(make_pair(-dis[v.to][v.v],make_pair(v.to,v.v)));
            }
            if(!v.v&&dis[v.to][o]>dis[u][o]+v.l/o){		//无速度限制
                dis[v.to][o]=dis[u][o]+v.l/o;
                lst[v.to][o]=make_pair(u,o);
                pq.emplace(make_pair(-dis[v.to][o],make_pair(v.to,o)));
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&t);
    t++;
    for(int i=1;i<=m;i++){
        int u,v,l,d;
        scanf("%d%d%d%d",&u,&v,&l,&d);
        u++;v++;
        g[u].emplace_back(v,l,d);
    }
    bfs();
    pair<int,int> now;
    double maxn=2e9;
    for(int i=1;i<M;i++){
        if(dis[t][i]<maxn){
            maxn=dis[t][i];
            now=make_pair(t,i);
        }
    }
    while(now.first){
        ans.push_back(now.first-1);
        now=lst[now.first][now.second];
    }
    reverse(ans.begin(),ans.end());
    // reverse(ans.begin(),ans.back());
    for(auto v:ans) printf("%d ",v);
    return 0;
}

标签:pq,int,短路,leq,分层,pair,图求,make,dis
From: https://www.cnblogs.com/imfbustxhf/p/18526082

相关文章

  • 矩阵快速幂加速最短路
    矩阵快速幂加速最短路通常用来优化Floyd的实现[NOIOnline#1入门组]魔法题目描述C国由$n$座城市与$m$条有向道路组成,城市与道路都从$1$开始编号,经过$i$号道路需要$t_i$的费用。现在你要从$1$号城市出发去$n$号城市,你可以施展最多$k$次魔法,使得通过下一条......
  • 迷宫问题(最短路径)——分别用DFS、BFS解决
    目录问题描述利用DFS(深度优先搜索)求解利用BFS(广度优先搜索)求解问题描述定义一个二维数组N*M,如5 × 5数组下所示:int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};它表示一个迷宫,其中的......
  • 【笔记/模板】Johnson全源最短路
    模板题目www.luogu.com.cn//Problem:P5905【模板】全源最短路(Johnson)//Contest:Luogu//URL:https://www.luogu.com.cn/problem/P5905//MemoryLimit:128MB//TimeLimit:1000ms////PoweredbyCPEditor(https://cpeditor.org)#include<bits/stdc++.h>......
  • 计算机网络:网络层 —— 开放最短路径优先 OSPF
    文章目录路由选择协议动态路由协议开放最短路径优先OSPF链路状态OSPF路由器邻居关系的建立和维护链路状态通告链路状态更新分组链路状态数据库OSPF的五种分组类型OSPF的基本工作过程多点接入网络中的OSPF路由器OSPF划分区域OSPF区域的类型OSPF区域的相关概念路......
  • AP3464 包含多重保护功能:过温保护,输出短路保护和输入欠压/过压保护等。
    产品描述AP5103是一款效率高,稳定可靠的LED灯恒流驱动控制芯片,内置高精度比较器,固定关断时间控制电路,恒流驱动电路等,特别适合大功率LED恒流驱动。AP5103采用ESOP8封装,散热片内置接SW脚,通过调节外置电流检测的电阻值来设置流过LED灯的电流,支持外加电压线性调光,最大电......
  • R语言贝叶斯分层、层次Hierarchical Bayesian模型的房价数据空间分析
    原文链接:https://tecdat.cn/?p=38077原文出处:拓端数据部落公众号本文主要探讨了贝叶斯分层模型在分析区域数据方面的应用,以房价数据为例,详细阐述了如何利用R帮助客户进行模型拟合、分析及结果解读,展示了该方法在处理空间相关数据时的灵活性和有效性。一、贝叶斯分层模型概述贝......
  • 最短路
    Floyd算法BFS求01最短路题目链接对于边权只有0和1的图,可以用BFS+deque求最短路具体做法:前端队列存由0边更新的点,后端存由1更新的点,每次松弛从前端取比较好想,由于是BFS,可以认为本层转移下,0边转移的点dis都相等,1边转移的点dis都相等(不一定正确),那么从前面取出来的点通过0边松弛......
  • 《 C++ 修炼全景指南:十七 》彻底攻克图论!轻松解锁最短路径、生成树与高效图算法
    摘要1、引言1.1、什么是图?图(Graph)是计算机科学和离散数学中一种重要的数据结构,用来表示一组对象之间的关系。一个图由顶点(也称为节点,Vertex)和边(Edge)组成。顶点表示实体,而边则表示实体之间的关联或连接关系。根据边的性质,图可以分为无向图和有向图。在无向图中,边没有方向......
  • 数据仓库分层解析
    目录一、数据仓库为什么要分层二、数据仓库怎么分层1、ODS(OperationalDataStore):数据源层2、DW(DataWarehouse): 数据仓库层2.1、DWD(DataWarehouseDetail):数据明细层2.2、DWM(DataWareHouseMidddle):数据中间层2.3、DWS(DataWareHouseService):数据服务层3、ADS(Applica......