<题目链接>
题目大意:
有N个城市,这些城市之间有M条有向边,每条边有权值,能够选择K条边 边权置为0,求1到N的最短距离。
解题分析:
分层图最短路模板题,将该图看成 K+1 层图,然后具体解析见代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define INF 0x7ffffffffff; ; ; typedef long long ll; int n,m,k,tot,cnt; int head[M]; ]; struct EDGE{ int to; int next; ll val; }edge[M<<]; struct NODE{ int loc,cal; //loc代表该点的标号,cal代表该点所在的层数,这两个变量可以确定分层图中所有点的位置 ll dist; bool operator <(const NODE &tmp)const{ return dist>tmp.dist; } NODE(,,ll w=){ loc=a,cal=b,dist=w; } }d[N][]; void init(){ cnt=; memset(head,-,sizeof(head)); } void add(int u,int v,int w){ edge[++cnt].to=v,edge[cnt].val=w; edge[cnt].next=head[u],head[u]=cnt; } void dij(){ memset(vis,false,sizeof(vis)); ;i<=n;i++){ ;j<=k;j++){ d[i][j].dist=INF; //将所有点到起点的距离初始化为无穷大 } } d[][].dist=; priority_queue<NODE>q; q.push(NODE(,,d[][].dist)); while(!q.empty()){ NODE now=q.top(); q.pop(); int tmp1=now.loc,tmp2=now.cal; if(vis[tmp1][tmp2])continue; vis[tmp1][tmp2]=true; for(int i=head[tmp1];~i;i=edge[i].next){ int v=edge[i].to; ll cost=edge[i].val; if(d[v][tmp2].dist>d[tmp1][tmp2].dist+cost){ //在同一层中进行普通的松弛操作,表示当前道路的权值不用置为0 d[v][tmp2].dist=d[tmp1][tmp2].dist+cost; q.push(NODE(v,tmp2,d[v][tmp2].dist)); } <=k&&d[v][tmp2+].dist>d[tmp1][tmp2].dist){ //没有加上cost,代表 tmp1-->v 这段路的权值置为0 d[v][tmp2+].dist=d[tmp1][tmp2].dist; q.push(NODE(v,tmp2+,d[v][tmp2+].dist)); } } } } int main(){ int T;scanf("%d",&T); while(T--){ init(); scanf("%d%d%d",&n,&m,&k); ;i<=m;i++){ int u,v;ll w; scanf("%d%d%lld",&u,&v,&w); add(u,v,w); } dij(); ll mn=INF; ;i<=k;i++){ //在所有层中选取最短的情况 mn=min(mn,d[n][i].dist); } printf("%lld\n",mn); } ; }
2018-09-12
ACM-ICPC 2018 南京赛区网络预赛 L 【分层图最短路】的更多相关文章
-
ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze
262144K There are NN cities in the country, and MM directional roads from uu to v(1\le u, v\le n)v ...
-
ACM-ICPC 2018 南京赛区网络预赛 L题(分层最短路)
题目链接:https://nanti.jisuanke.com/t/31001 题目大意:给出一个含有n个点m条边的带权有向图,求1号顶点到n号顶点的最短路,可以使<=k条任意边的权值变为0. ...
-
ACM-ICPC 2018 南京赛区网络预赛 L题(分层图,堆优化)
题目链接: https://nanti.jisuanke.com/t/31001 超时代码: #include<bits/stdc++.h> using namespace std; # ...
-
ACM-ICPC 2018 南京赛区网络预赛 L.Magical Girl Haze(分层最短路)
There are N cities in the country, and M directional roads from u to v(1≤u,v≤n). Every road has a di ...
-
ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze 最短路+分层图
类似题解 There are NN cities in the country, and MM directional roads from uu to v(1\le u, v\le n)v(1≤u, ...
-
ACM-ICPC 2018 南京赛区网络预赛 - L Magical Girl Haze (分层迪杰斯特拉)
题意:N个点,M条带权有向边,求可以免费K条边权值的情况下,从点1到点N的最短路. 分析:K<=10,用dist[i][j]表示从源点出发到点i,免费j条边的最小花费.在迪杰斯特拉的dfs过程中 ...
-
ACM-ICPC 2018 南京赛区网络预赛 L &;&; BZOJ 2763 分层最短路
https://nanti.jisuanke.com/t/31001 题意 可以把k条边的权值变为0,求s到t的最短路 解析 分层最短路 我们建立k+1层图 层与层之间边权为0,i 向 i+1层转 ...
-
【ACM-ICPC 2018 南京赛区网络预赛 L】Magical Girl Haze
[链接] 我是链接,点我呀:) [题意] 在这里输入题意 [题解] 定义dis[i][j]表示到达i这个点. 用掉了j次去除边的机会的最短路. dis[1][0]= 0; 在写松弛条件的时候. 如果用 ...
-
ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze (分层dijkstra)
There are NN cities in the country, and MMdirectional roads from uu to v(1\le u, v\le n)v(1≤u,v≤n). ...
随机推荐
-
UML中的六大关系(转)
UML定义的关系主要有六种:依赖.继承.关联.实现.聚合和组合.这些类间关系的理解和使用是掌握和应用UML的关键,而也就是这几种关系,往往会让初学者迷惑.这里给出这六种主要UML关系的说明和类图描述, ...
-
《简明python教程》笔记一
读<简明Python教程>笔记: 本书的官方网站是www.byteofpython.info 安装就不说了,网上很多,这里就记录下我在安装时的问题,首先到python官网下载,选好安装路 ...
-
Web前端开发基础 第四课(CSS小技巧1)
垂直居中-父元素高度确定的单行文本 父元素高度确定的单行文本的竖直居中的方法是通过设置父元素的 height 和 line-height 高度一致来实现的.如下代码: <div class=&q ...
-
imageview圆角的实现
介绍一种简单的.另类的实现,就是把图片在显示前处理成圆角的,但是不改变存储的图片.相当于经过了图像过滤. 需要调用的图像工具类是 package com.gaosi.util; /** * @auth ...
-
Axis2在Web项目中整合Spring
一.说明: 上一篇说了Axis2与Web项目的整合(详情 :Axis2与Web项目整合)过程,如果说在Web项目中使用了Spring框架,那么又改如何进行Axis2相关的配置操作呢? 二.Axis2 ...
-
iOS7 iOS8 毛玻璃效果的分别实现
iOS8用系统的, iOS7用第三方的(效果还是挺快的.) https://github.com/KiranPatel-iOS/KPBlurEffect [_headBGIV sd_setImageW ...
-
Nginx配置中运行与启动的详细介绍【转】
原文:http://developer.51cto.com/art/201003/190944.htm 我们在进行Nginx配置的时候会出现很多不明白的地方,其实有些时候只要换一个思维的方式就能找多你 ...
-
375. Guess Number Higher or Lower II
最后更新 四刷? 极大极小算法..还是叫极小极大的.. 首先要看怎么能保证赢. 比如2个数,猜第一个猜第二个都能保证下一轮我们赢定了,为了少交钱,我们猜小的. 比如3个数,猜第二个才能保证下一轮再猜一 ...
-
Tomcat学习笔记(二)—— 一个简单的Servlet容器
1.简介:Servlet编程是通过javax.Servlet和javax.servlet.http这两个包的类和接口实现的,其中javax.servlet.Servlet接口至关重要,所有的Servl ...
-
【ABP.Net】1.创建项目&;介绍框架结构
既然已经打开这个页面了,我就不介绍什么是ABP了.哈哈哈,如果想知道,请移驾.反正我是不说. 1.首先打开https://aspnetboilerplate.com/Templates 下载所需要的A ...