当前位置:网站首页>牛客:飞行路线(分层图+最短路)
牛客:飞行路线(分层图+最短路)
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);
}
边栏推荐
- 基于STM32MP157调试MIPI-DSI屏幕
- Take you through the normalization flow of GaN
- 27. remove elements
- 力扣78:子集
- The method of judging whether triode can amplify AC signal
- navicat定时任务无效
- DNS协议及其DNS完整的查询过程
- @Resource和@Autowired注解的不同,为什么推荐@Resource?
- Use the frame statistics function of the message and waveform recording analyzer royalscope to troubleshoot the accidental faults of the CAN bus
- 黑点==白点(MST)
猜你喜欢
消息中间件之ActiveMQ的基本使用
Five causes of PCB board deformation and six solutions 2021-10-08
Three Siemens fire-fighting hosts fc18 are equipped with can optical transceiver for optical fiber redundant ring network networking test
Manufacturing process of PCB 2021-10-11
Machine learning notes linear regression of time series
Modular programming of wireless transmission module nRF905 controlled by single chip microcomputer
VSCode很好,但我以后不会再用了
OpenCV每日函数 结构分析和形状描述符(8) fitLine函数 拟合直线
Knowledge sharing 𞓜 conventional laminated structure of six layer PCB
Do you know why the PCB produces tin beads? 2021-09-30
随机推荐
opencv最小值滤波(不局限于图像)
JDBC-DAO层实现
【论文学习】《VQMIVC》
【Unexpected token o in JSON at position 1出错原因及解决方法】
[little knowledge] PCB proofing process
机器学习笔记 - 时间序列的线性回归
C get the version number of exe - file version and assembly version
判断用户是否是第一次进入某个页面
取消word文档中某些页面的页眉
MySQL简单权限管理
Sword finger offer II 027 Palindrome linked list
用函数的递归来解决几道有趣的题
WinForm implementation window is always at the top level
将数据导入到MATLAB
Introduction to the main functions of the can & canfd comprehensive test and analysis software lkmaster of the new usbcan card can analyzer
Bicubic difference
剑指 Offer II 027. 回文链表
Terms and concepts related to authority and authentication system
Basic use of ActiveMQ in Message Oriented Middleware
挖掘微生物暗物质——新思路