ACM-ICPC 2018 南京赛区网络预赛 L Magical Girl Haze(分层图+Dijkstra堆优化)

本文主要是介绍ACM-ICPC 2018 南京赛区网络预赛 L Magical Girl Haze(分层图+Dijkstra堆优化),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:https://nanti.jisuanke.com/t/31001

 

题目大意:给一张有向图,给把k条边权值变0的机会,问1~n最短路

 

题目思路:把原先的dist改成二维,第二维表示删几条边, 然后迪杰斯特拉的松弛也分成两部分,一个是本身的松弛,还有一个是送到下一层,由于每一层内,最小的那个松弛以后他松弛的点继续松弛,这样就等效于只删了一条边,如此一直松弛。

 

以下是代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN 100005
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
struct Edge{int to,w,next;
}edge[MAXN<<1];
struct node{int v,c,cnt;bool operator <(const node &r)const{return c>r.c;}
}a;
int head[MAXN],tot,k;
void addedge(int u,int v,int w){edge[tot].to=v,edge[tot].w=w,edge[tot].next=head[u],head[u]=tot++;
}
bool vis[MAXN][15];
ll dist[MAXN][15];
void dij(int n,int s){memset(vis,false,sizeof(vis));memset(dist,0x3f,sizeof(dist));priority_queue<node>q;while(!q.empty())q.pop();dist[s][0]=0;a.v=s,a.c=a.cnt=0;q.push(a);while(!q.empty()){node temp=q.top();q.pop();int u=temp.v,cnt=temp.cnt;if(vis[u][cnt])continue;vis[u][cnt]=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to,w=edge[i].w;if(!vis[v][cnt]&&dist[v][cnt]>dist[u][cnt]+w){dist[v][cnt]=dist[u][cnt]+w;a.v=v,a.c=dist[v][cnt],a.cnt=cnt;q.push(a);}if(cnt<k&&dist[v][cnt+1]>dist[u][cnt]){dist[v][cnt+1]=dist[u][cnt];a.v=v,a.c=dist[u][cnt],a.cnt=cnt+1;q.push(a);}}}
}
int main()
{int t,n,m,u,v,w;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);tot=0;memset(head,-1,sizeof(head));while(m--){scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);}dij(n,1);printf("%lld\n",dist[n][k]);}return 0;
}

 

这篇关于ACM-ICPC 2018 南京赛区网络预赛 L Magical Girl Haze(分层图+Dijkstra堆优化)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/914067

相关文章

Linux中压缩、网络传输与系统监控工具的使用完整指南

《Linux中压缩、网络传输与系统监控工具的使用完整指南》在Linux系统管理中,压缩与传输工具是数据备份和远程协作的桥梁,而系统监控工具则是保障服务器稳定运行的眼睛,下面小编就来和大家详细介绍一下它... 目录引言一、压缩与解压:数据存储与传输的优化核心1. zip/unzip:通用压缩格式的便捷操作2.

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

Linux网络配置之网桥和虚拟网络的配置指南

《Linux网络配置之网桥和虚拟网络的配置指南》这篇文章主要为大家详细介绍了Linux中配置网桥和虚拟网络的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、网桥的配置在linux系统中配置一个新的网桥主要涉及以下几个步骤:1.为yum仓库做准备,安装组件epel-re

python如何下载网络文件到本地指定文件夹

《python如何下载网络文件到本地指定文件夹》这篇文章主要为大家详细介绍了python如何实现下载网络文件到本地指定文件夹,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下...  在python中下载文件到本地指定文件夹可以通过以下步骤实现,使用requests库处理HTTP请求,并结合o

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

PyTorch高级特性与性能优化方式

《PyTorch高级特性与性能优化方式》:本文主要介绍PyTorch高级特性与性能优化方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、自动化机制1.自动微分机制2.动态计算图二、性能优化1.内存管理2.GPU加速3.多GPU训练三、分布式训练1.分布式数据

Maven 插件配置分层架构深度解析

《Maven插件配置分层架构深度解析》:本文主要介绍Maven插件配置分层架构深度解析,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Maven 插件配置分层架构深度解析引言:当构建逻辑遇上复杂配置第一章 Maven插件配置的三重境界1.1 插件配置的拓扑

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

C#实现高性能Excel百万数据导出优化实战指南

《C#实现高性能Excel百万数据导出优化实战指南》在日常工作中,Excel数据导出是一个常见的需求,然而,当数据量较大时,性能和内存问题往往会成为限制导出效率的瓶颈,下面我们看看C#如何结合EPPl... 目录一、技术方案核心对比二、各方案选型建议三、性能对比数据四、核心代码实现1. MiniExcel