发门网
刷题记录:牛客NC26257小雨坐地铁 [分层图跑最短路]
创始人
2024-05-02 20:15:00
0次

传送门:牛客

题目描述:

题目暂略
输入:
5 2 1 4
2 2 3 1 3 5
2 1 4 2 3 4 5
输出:
7

一道分层图的经典题型,可以细细体会,这道题模拟出了经典的分层图题型

主要思路:

  1. 首先我们那道这道题应该不难想到最短路(这是显然的吧).大多数人应该都是卡在了建边的部分.每一条线路各自的边是好建的,不过是双向边而已.不好想到的是如何完成换线的操作.这个似乎很难完成了
  2. 此时我们仔细想一下我们的换线过程,不就是在地铁站上下车吗.也就是在地铁站下车是不花钱的,上车是花钱的,那么我们是不是能将我们的地铁站看成一个个图中的节点呢,也就是我们的不同地铁线路中有各自的节点,然后我们的地铁站也是一个个节点,然后我们是通过不同线路中的各个节点在不同地铁站中穿梭
  3. 也就是我们的不同地铁线建图并且对应的地铁编号都再与各自的地铁站继续连线.这样我们的地铁就可以下车(不花钱),到地铁站再由地铁站上车到其他线路了(花钱).并且为了方便起见,我们可以假定我们的每一条线路中的编号不再是1−>n1->n1−>n,而是n∗i+u−>n∗i+vn*i+u->n*i+vn∗i+u−>n∗i+v,这样的话建图更加清楚明白.

如果还是不太明白的话,我就样例举个栗子吧:

在这里插入图片描述
最终建图情况如上,中间的12345是地铁站,上下分别是地铁线路

这种分层建图的算法就是我们的分层图了,接下来直接跑dijkstradijkstradijkstra即可

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
struct Node{int v,w;
};
struct heapnode{int u,d;bool operator<(const heapnode &rhs) const {return d>rhs.d;}
};
int dis[maxn],vis[maxn];
vectoredge[maxn];
int n,m;
void dij(int S) {for(int i=1;i<=n*(m+2);i++) dis[i]=inf;dis[S]=0;priority_queueq;q.push({S,0});while(!q.empty()) {heapnode f=q.top();q.pop();int u=f.u;if(vis[u]) continue;vis[u]=1;for(int i=0;iint v=edge[u][i].v;if(dis[v]>dis[u]+edge[u][i].w) {dis[v]=dis[u]+edge[u][i].w;q.push({v,dis[v]});}}}
}
int s,t;
int main() {n=read();m=read();s=read();t=read();for(int i=1;i<=m;i++) {int ai=read(),bi=read(),ci=read();int U=read();int V;edge[n*i+U].push_back({U,0});edge[U].push_back({n*i+U,ai});for(int j=2;j<=ci;j++) {V=read();edge[U+n*i].push_back({V+n*i,bi});edge[V+n*i].push_back({U+n*i,bi});edge[n*i+V].push_back({V,0});edge[V].push_back({n*i+V,ai});U=V;}}dij(s);if(dis[t]==inf) printf("-1\n");else cout<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：[vue element-ui]JAVA POST请求

下一篇：mysql-JDBCDruid基本使用方法

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播，要解决的几个问题是：1&...
Windows10添加群晖磁盘... 在使用群晖NAS时，我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章，在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF，目录中的页码并非PDF中直接索引的页码...
Fluent中创建监测点 1 概述某些仿真问题，需要创建监测点，用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装（Wind... 前言：刚换了一台电脑，里面所有东西都需要重新配置，习惯了所...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
MFC文件操作  MFC提供了一个文件操作的基类CFile，这个类提供了一个没有缓存的二进制格式的磁盘...