题意:
给一个2e4带正边权的图,可以免费k个边,一条路径的花费为路径上边权最大值,问你1到n的最小花费
思路:
对于一个x,我们如果将大于等于x的边权全部免费,那么至少需要免费的边的数量就是
“设大于等于x的边权的边长为1,其余为0,起点到终点的最短路”
然后如果这个得到的最短路,也就是我们所需要免费的边数小于等于k的话,就可以满足题意了(check)
思考一下可以发现对于任何条件,都存在某一个p,当x取[p, inf]的任意值时,都是可以满足题意的
于是我们就可以二分x并check了
得到p之后跑一遍最短路上的最大值,就是答案了(我每次check成功后记录了一次pre)
这题要注意不连通时候的情况输出-1
update:今天仔细想了一下,其实二分的就是ans+1,最后只需要输出max(ans-1,0)就是答案
然后二分+最短路也只能用于这种路径上边权最大值为费用的题了
代码:
有点像西安邀请赛的二分最短路啊
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
//#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 2e6+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f; const db pi = acos(-1.0); int n, m, k;
int dist[maxn];
struct node{
int id, d;
node(){}
node(int a,int b) {id = a; d = b;}
bool operator < (const node & a)const{
if(d == a.d) return id > a.id;
else return d > a.d;
}
};
vector<node>e[maxn];
PI pre[maxn];
PI tpre[maxn];
void dijkstra(int s, int ki){
for(int i = ; i <= n; i++) dist[i] = inf;//往往不够大 dist[s] = ;
priority_queue<node>q;
q.push(node(s, dist[s]));
while(!q.empty()){
node top = q.top();
q.pop();
if(top.d != dist[top.id]) continue;
for(int i = ; i < (int)e[top.id].size(); i++){
node x = e[top.id][i];
int d=;
if(x.d>=ki)d=;
if(dist[x.id] > top.d + d){
pre[x.id]=make_pair(top.id,x.d);
dist[x.id] = top.d + d;
q.push(node(x.id, dist[x.id]));
}
}
}
return;
}
int main(){
scanf("%d %d %d", &n, &m, &k);
int ans = -inf;
int l,r;
for(int i = ; i <= m; i++){
int x ,y,w;
scanf("%d %d %d", &x, &y, &w);
e[x].pb(node(y,w));
e[y].pb(node(x,w));
}
l=;r=+;
while(l<=r){
int mid = (l+r)>>;
dijkstra(,mid);
//printf("--%d %d %d ==%d\n",l,r,mid,dist[n]);
if(dist[n]<=k){
for(int i = ; i <= n; i++){
tpre[i]=pre[i];
}
r=mid-;
ans=mid;
}
else l=mid+;
}
//printf("%d\n",ans);
if(ans==-inf)return printf("-1"),;
int res = ;
for(int i = n; i != ; i = tpre[i].fst){
//printf("--%d %d %d\n",i, pre[i].fst, pre[i].sc);
int x = tpre[i].sc;
if(x>=ans)continue;
res = max(res, x);
}
printf("%d",res);
return ;
}
/*
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6 4 3 1
1 2 2
1 3 5
2 3 3
*/
BZOJ 1614 [Usaco2007 Jan]Telephone Lines架设电话线 (二分+最短路)的更多相关文章
-
BZOJ 1614: [Usaco2007 Jan]Telephone Lines架设电话线
题目 1614: [Usaco2007 Jan]Telephone Lines架设电话线 Time Limit: 5 Sec Memory Limit: 64 MB Description Farm ...
-
BZOJ 1614 [Usaco2007 Jan]Telephone Lines架设电话线:spfa + 二分【路径中最大边长最小】
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1614 题意: 给你一个无向图,n个点,m条边. 你需要找出一条从1到n的路径,使得这条路径 ...
-
BZOJ——1614: [Usaco2007 Jan]Telephone Lines架设电话线
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1930 Solved: 823[Submit][Status][Discuss] Description ...
-
bzoj 1614: [Usaco2007 Jan]Telephone Lines架设电话线【二分+spfa】
二分答案,然后把边权大于二分值的的边赋值为1,其他边赋值为0,然后跑spfa最短路看是否满足小于等于k条边在最短路上 #include<iostream> #include<cstd ...
-
[Usaco2007 Jan]Telephone Lines架设电话线(最短路,二分)
[Usaco2007 Jan]Telephone Lines架设电话线 Description FarmerJohn打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向 ...
-
[Usaco2007 Jan]Telephone Lines架设电话线[二分答案+最短路思想]
Description Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向电信公司支付一定的费用. FJ的农场周围分布着N(1 <= N ...
-
【bzoj1614】[Usaco2007 Jan]Telephone Lines架设电话线 二分+SPFA
题目描述 Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向电信公司支付一定的费用. FJ的农场周围分布着N(1 <= N <= 1 ...
-
BZOJ1614: [Usaco2007 Jan]Telephone Lines架设电话线
1614: [Usaco2007 Jan]Telephone Lines架设电话线 Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 892 Solved: ...
-
【bzoj1614】[Usaco2007 Jan]Telephone Lines架设电话线
题目描述 Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务.于是,FJ必须为此向电信公司支付一定的费用. FJ的农场周围分布着N(1 <= N < ...
随机推荐
-
android官方下拉刷新控件SwipeRefreshLayout的使用
可能开发安卓的人大多数都用过很多下拉刷新的开源组件,但是今天用了官方v4支持包的SwipeRefreshLayout觉得效果也蛮不错的,特拿出来分享. 简介:SwipeRefreshLayout组件只 ...
-
iOS之关于开发的那点破事(一)
前言: 前段时间,经理突然找我说:能不能在项目中对缓存的图片进行加密?当时就感到疑惑,就说:可以是可以,但为什么要这样做?有什么意义没? 我们都知道,apple使用的沙盒(sandbox)机制,这种机 ...
-
RDD中cache和persist的区别
通过观察RDD.scala源代码即可知道cache和persist的区别: def persist(newLevel: StorageLevel): this.type = { if (storage ...
-
Java学习笔记之==与equals
一.问题引入 Java测试两个变量是否相等有两种方式:==运算符和equals方法. 但是这二者完全一样吗?考虑下面程序: public class TestEqual { public static ...
-
Lucence.net索引技术 二
一. Lucene索引创建和优化 [版本2.9.0以上] Lucene索引的创建首先需要取得几个必须的对象: 1.分词器//可以采用其他的中文分词器 StandardAnalyzer analyzer ...
-
vue2.0 如何在hash模式下实现微信分享
最近又把vue的demo拿出来整理下,正好要做"微信分享"功能,于是遇到新的问题: 由于hash模式下,带有"#",导致微信分享的签证无效:当改成history ...
-
[Python]print vs sys.stdout.write
之前只是在项目中看到过,没怎么注意,正好跟对象一起看python学习手册,看到了这个部分于是来研究下. python版本 2.7.x os win7 print 一般就是执行脚本的时候,把信息直接 ...
-
RabbitMQ学习笔记(三) 发布与订阅
发布与订阅 在我们使用手机发送消息的时候,即可以选择给单个手机号码发送消息,也可以选择多个手机号码,群发消息. 前面学习工作队列的时候,我们使用的场景是一个消息只能被一个消费者程序实例接收并处理,但是 ...
-
一对多Excel自定义函数:SVLOOKUP
语法规则 该函数的语法规则如下: SVLOOKUP(lookup_value,table_array,col_index_num,nth_appearance,unique_value) 参数 简单说 ...
-
JS --- 本地保存localStorage、sessionStorage用法总结
JS的本地保存localStorage.sessionStorage用法总结 localStorage.sessionStorage是Html5的特性,IE7以下浏览器不支持 为什么要掌握localS ...