POJ3662 Telephone Lines（二分+最短路）

水深无声 2021-11-17 03:44 204阅读 0赞

## 题意：求一条路径从1到n使第k+1大的边最小。 ##

## 分析：双端队列BFS，详见《算法竞赛进阶指南》P356、P120。 ##

## 代码： ##

#include <deque>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 1006, P = 20006;
    int n, p, k, maxl = 0, d[N];
    int Head[N], Edge[P], Next[P], Leng[P], tot = 0;
    deque<int> q;
    bool v[N];
    
    inline void add(int x, int y, int z) {
    	Edge[++tot] = y;
    	Leng[tot] = z;
    	Next[tot] = Head[x];
    	Head[x] = tot;
    }
    
    int bfs(int now) {
    	memset(d, 0x3f, sizeof(d));
    	memset(v, 0, sizeof(v));
    	d[1] = 0;
    	q.push_back(1);
    	while (q.size()) {
    		int x = q.front();
    		q.pop_front();
    		if (v[x]) continue;
    		v[x] = 1;
    		for (int i = Head[x]; i; i = Next[i]) {
    			int y = Edge[i], z = Leng[i];
    			if (v[y]) continue;
    			if (z > now) {
    				if (d[y] <= d[x] + 1) continue;
    				d[y] = d[x] + 1;
    				q.push_back(y);
    			} else {
    				if (d[y] <= d[x]) continue;
    				d[y] = d[x];
    				q.push_front(y);
    			}
    		}
    	}
    	return d[n];
    }
    
    int main() {
    	cin >> n >> p >> k;
    	for (int i = 1; i <= p; i++) {
    		int x, y, z;
    		scanf("%d%d%d", &x, &y, &z);
    		add(x, y, z);
    		add(y, x, z);
    		maxl = max(maxl, z);
    	}
    	if (bfs(maxl) > k) {
    		puts("-1");
    		return 0;
    	}
    	int l = 0, r = maxl;
    	while (l < r) {
    		int mid = (l + r) >> 1;
    		if (bfs(mid) > k) l = mid + 1;
    		else r = mid;
    	}
    	cout << l << endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，204人围观）

还没有评论，来说两句吧...

相关阅读

相关最短路

<table> <tbody> <tr> <td> <h2>最短路</h2> <strong>Time Limit: 5000/1000 MS (Java/O

向右看齐/ 2024年02月18日 22:54/ 0 赞/ 45 阅读

相关 POJ 2502 最短路

题意略。思路：本题有必要记录一下。首先是dijkstra求最短路没问题，关键是在建图的时候，地铁沿线还要加上行走互达的边，因为： ![1161042-20190819

﹏ヽ暗。殇╰゛Y/ 2023年08月17日 16:37/ 0 赞/ 109 阅读

相关最短路

\[hdu 1599\] ([http://acm.hdu.edu.cn/showproblem.php?pid=1599][http_acm.hdu.edu.cn_showp

红太狼/ 2022年08月04日 08:28/ 0 赞/ 166 阅读

相关 hdu 1839 二分搜索+dijkstra最短路

[点击打开链接][Link 1] 题意: 给定一个无向图, 顶点从1-n, 给定m条边, 每条边有两个值, 一是这条边的最大容量, 二是经过这条边需要的时间, 要求从1顶点开

小灰灰/ 2022年07月28日 00:23/ 0 赞/ 155 阅读

相关最短路

队列+松弛操作读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d\[v\]变小），那么就更新，另外，如果

忘是亡心i/ 2022年06月11日 04:06/ 0 赞/ 206 阅读

相关最短路

一下模板均已通过HDUOJ 2544 程序设计竞赛队空间和时间复杂度要求都很高，所以朴素的Dijkstra[算法][Link 1]无论时间还是空间，效率都很低。所以，一般

淡淡的烟草味﹌/ 2022年06月09日 04:28/ 0 赞/ 242 阅读

相关最短路

最短路典型用途：交通网络的问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？交通网络用有向网来表示：顶点——表示城市，弧——表示两个城

淡淡的烟草味﹌/ 2022年03月18日 12:35/ 0 赞/ 253 阅读

相关最短路

Floyed [http://codevs.cn/problem/1077/][http_codevs.cn_problem_1077] include<cstdi

﹏ヽ暗。殇╰゛Y/ 2021年11月18日 00:30/ 0 赞/ 292 阅读

相关 POJ3662 Telephone Lines（二分+最短路）

题意：求一条路径从1到n使第k+1大的边最小。分析：双端队列BFS，详见《算法竞赛进阶指南》P356、P120。代码： include <dequ

水深无声/ 2021年11月17日 03:44/ 0 赞/ 205 阅读

相关最短路

复习下图论算法 1. 邻接表的Dijkstra ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] /

冷不防/ 2021年11月02日 14:24/ 0 赞/ 448 阅读