当前位置:网站首页>牛客:飞行路线(分层图+最短路)
牛客:飞行路线(分层图+最短路)
2022-06-25 06:43:00 【mfy的1号小迷弟】
牛客:飞行路线(分层图+最短路)
题意:
一个带边权的图,求从s到t的最短距离,可以忽略k条边的权值。
2 < = n < = 10000 , 1 < = m < = 50000 , 0 < = k < = 10 2<=n<=10000,1<=m<=50000,0<=k<=10 2<=n<=10000,1<=m<=50000,0<=k<=10
思路:
因为k很小,可以想不 到分层图,把原图看成k层,每层完全一样,再建新边把每层连起来,对于第一层的从x到y,把x每层对应的点和下一层的y连一条权值为0的边,把y每层对应的点和下一层的x连一条权值为0的边。这样从某层的x到下一层的y就表示用了一次k
再跑最短路
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
typedef pair<int,int>pii;
const int maxn=3e6+5;
int s,n,m,t,k,d,dis[maxn],vis[maxn],head[maxn],w[maxn],to[maxn],nex[maxn];
void add(int x,int y,int z){
nex[++d]=head[x];
to[d]=y;
w[d]=z;
head[x]=d;
}
void dij(){
memset(dis,INF,sizeof(dis));
dis[s]=0;
priority_queue<pii,vector<pii>,greater<pii>>p;
p.push({
0,s});
while(!p.empty()){
int x=p.top().second;
p.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(dis[y]>dis[x]+w[i]){
dis[y]=dis[x]+w[i];
p.push({
dis[y],y});
}
}
}
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
for(int i=1,x,y,z;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
for(int j=1;j<=k;j++){
add(x+j*n,y+j*n,z);
add(y+j*n,x+j*n,z);
add(x+(j-1)*n,y+j*n,0);
add(y+(j-1)*n,x+j*n,0);
}
}
dij();
int ans=INF;
for(int i=0;i<=k;i++){
ans=min(ans,dis[i*n+t]);
}
printf("%d\n",ans);
}
边栏推荐
- 基于RBAC 的SAAS系统权限设计
- Anaconda navigator启动慢的一个解决方法
- 力扣78:子集
- MySQL简单权限管理
- Can transparent cloud gateway caniot and candtu record can messages and send and receive can data remotely
- Force deduction 76 questions, minimum covering string
- Atlassian confluence漏洞分析合集
- 年后求职找B端产品经理?差点把自己坑惨了......
- NPM install reports an error: gyp err! configure error
- 【QT】qtcreator便捷快捷键以及QML介绍
猜你喜欢
传统的IO存在什么问题?为什么引入零拷贝的?
This article uses pytorch to build Gan model!
新版USBCAN卡CAN分析仪的CAN&CANFD综合测试分析软件LKMaster主要功能介绍
Do you know why the PCB produces tin beads? 2021-09-30
Share the process requirements for single-layer flexible circuit board
Importer des données dans MATLAB
How to use ad wiring for PCB design?
Modular programming of LCD1602 LCD controlled by single chip microcomputer
微信小程序开通客服消息功能开发
将数据导入到MATLAB
随机推荐
Bicubic difference
Four software 2021-10-14 suitable for beginners to draw PCB
年后求职找B端产品经理?差点把自己坑惨了......
OpenCV每日函数 结构分析和形状描述符(8) fitLine函数 拟合直线
Startup, shutdown and restart of Oracle and MySQL on Linux
What are the problems with traditional IO? Why is zero copy introduced?
Can bus working condition and signal quality "physical examination"
【红旗杯?】补题
Keil and Proteus joint commissioning
C control refresh
【论文学习】《VQMIVC》
Fairmot yolov5s to onnx
使用Adobe Acrobat Pro调整PDF页面为统一大小
How to use ad wiring for PCB design?
SSL证书免费获取教程
三台西门子消防主机FC18配套CAN光端机进行光纤冗余环网组网测试
一次弄清楚 Handler 可能导致的内存泄漏和解决办法
420-二叉树的层序遍历2(429. N 叉树的层序遍历、515.在每个树行中找最大值、116.填充每个节点的下一个右侧节点指针、104.二叉树的最大深度、111.二叉树的最小深度)
SCM Project Training
Understand the reasons for impedance matching of PCB circuit board 2021-10-07