架設電話線 架設電話線 ⁡ \operatorname{架設電話線} 架設電話線 & ⁡ \operatorname{\&} &

架設電話線 ⁡ \operatorname{架設電話線} 架設電話線

& ⁡ \operatorname{\&} &

Telephone Lines S ⁡ \operatorname{Telephone\ Lines\ S} Telephone Lines S

題目連結：

1. 架設電話線： SSL比賽 1466 ⁡ \operatorname{SSL比賽\ 1466} SSL比賽 1466

2. Telephone Lines S： l u o g u   1948 luogu\ 1948 luogu 1948

架 設 電 話 線 ： 架設電話線： 架設電話線：

題目

Farmer John 打算将電話線引到自己的農場，但電信公司并不打算為他提供免費服務。于是， FJ 必須為此向電信公司支付一定的費用。

FJ 的農場周圍分布着 N ( 1 < = N < = 1 , 000 ) N(1 <= N <= 1,000) N(1<=N<=1,000) 根按 1.. N 1..N 1..N 順次編号的廢棄的電話線杆，任意兩根電話線杆間都沒有電話線相連。一共 P ( 1 < = P < = 10 , 000 ) P(1 <= P <= 10,000) P(1<=P<=10,000) 對電話線杆間可以拉電話線，其餘的那些由于隔得太遠而無法被連接配接。第 i i i 對電話線杆的兩個端點分别為 A i A_i Ai​ 、 B i B_i Bi​ ，它們間的距離為 L i ( 1 < = L i < = 1 , 000 , 000 ) L_i (1 <= L_i <= 1,000,000) Li​(1<=Li​<=1,000,000) 。資料中保證每對 { A i ， B i } \{A_i，B_i\} {Ai​，Bi​} 最多隻出現 1 1 1 次。編号為 1 1 1 的電話線杆已經接入了全國的電話網絡，整個農場的電話線全都連到了編号為 N N N 的電話線杆上。也就是說， FJ 的任務僅僅是找一條将 1 1 1 号和 N N N 号電話線杆連起來的路徑，其餘的電話線杆并不一定要連入電話網絡。

經過談判，電信公司最終同意免費為 FJ 連結 K ( 0 < = K < N ) K(0 <= K < N) K(0<=K<N) 對由 FJ 指定的電話線杆。對于此外的那些電話線， FJ 需要為它們付的費用，等于其中最長的電話線的長度（每根電話線僅連結一對電話線杆）。如果需要連結的電話線杆不超過 K K K對 ，那麼 F J FJ FJ 的總支出為 0 0 0 。

請你計算一下， FJ 最少需要在電話線上花多少錢。

樣例解釋（樣例在下面）

輸入解釋

一共有 5 5 5 根廢棄的電話線杆。電話線杆 1 1 1 不能直接與電話線杆 4 4 4 、 5 5 5 相連。電話線杆 5 5 5 不能直接與電話線杆 1 1 1 、 3 3 3 相連。其餘所有電話線杆間均可拉電話線。電信公司可以免費為 FJ 連結一對電話線杆。

輸出解釋

FJ 選擇如下的連結方案： 1 −  ⁣ ⁣ > 3 1-\!\!>3 1−>3 ； 3 −  ⁣ ⁣ > 2 3-\!\!>2 3−>2 ； 2 −  ⁣ ⁣ > 5 2-\!\!>5 2−>5 ，這 3 3 3 對電話線杆間需要的電話線的長度分别為 4 4 4 、 3 3 3 、 9 9 9 。 FJ 讓電信公司提供那條長度為 9 9 9 的電話線，于是，他所需要購買的電話線的最大長度為 4 4 4 。

資料點 1 ∼ 4 1\sim 4 1∼4 ： N < = 10 , P < = 20 ; N<=10,P<=20; N<=10,P<=20;

資料點 5 ∼ 6 5\sim 6 5∼6 ： N < = 50 , P < = 200 ; N<=50,P<=200; N<=50,P<=200;

資料點 7 ∼ 9 7\sim 9 7∼9 ： N < = 1000 , P < = 1000 ; N<=1000,P<=1000; N<=1000,P<=1000;

資料點 10 ∼ 11 10\sim 11 10∼11 ： N < = 1000 , P < = 5000 ; N<=1000,P<=5000; N<=1000,P<=5000;

資料點 12 ∼ 13 12\sim 13 12∼13 ： N < = 1000 , P < = 10000 ; N<=1000,P<=10000; N<=1000,P<=10000;

T e l e p h o n e   L i n e s   S ： Telephone\ Lines\ S： Telephone Lines S：

題目

多年以後，笨笨長大了，成為了電話線布置師。由于地震使得某市的電話線全部損壞，笨笨是負責接到震中市的負責人。該市周圍分布着 N ( 1 < = N < = 1000 ) N(1<=N<=1000) N(1<=N<=1000) 根據 1 … … n 1……n 1……n 順序編号的廢棄的電話線杆，任意兩根線杆之間沒有電話線連接配接，一共有 p ( 1 < = p < = 10000 ) p(1<=p<=10000) p(1<=p<=10000) 對電話杆可以拉電話線。其他的由于地震使得無法連接配接。

第 i i i 對電線杆的兩個端點分别是 a i , b i a_i,b_i ai​,bi​ ，它們的距離為 l i ( 1 < = l i < = 1000000 ) l_i(1<=li<=1000000) li​(1<=li<=1000000) 。資料中每對 ( a i , b i ) (a_i,b_i) (ai​,bi​) 隻出現一次。編号為 1 1 1 的電話杆已經接入了全國的電話網絡，整個市的電話線全都連到了編号 N N N 的電話線杆上。也就是說，笨笨的任務僅僅是找一條将 1 1 1 号和 N N N 号電線杆連起來的路徑，其餘的電話杆并不一定要連入電話網絡。

電信公司決定支援災區免費為此市連接配接 k k k 對由笨笨指定的電話線杆，對于此外的那些電話線，需要為它們付費，總費用決定于其中最長的電話線的長度(每根電話線僅連接配接一對電話線杆)。如果需要連接配接的電話線杆不超過 k k k 對，那麼支出為 0. 0. 0.

請你計算一下，将電話線引導震中市最少需要在電話線上花多少錢？

共 同 ： 共同： 共同：

輸入

第 1 1 1 行： 3 3 3 個用空格隔開的整數： N N N ， P P P ，以及 K K K

第 2... P + 1 2...P+1 2...P+1 行： 第 i + 1 i+1 i+1 行為 3 3 3 個用空格隔開的整數： A i A_i Ai​ ， B i B_i Bi​ ， L i L_i Li​

輸出

第 1 1 1 行： 輸出 1 1 1 個整數，為 FJ 在這項工程上的最小支出。如果任務不可能完成，輸出 − 1 -1 −1 。

樣例輸入

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
           

樣例輸出

思路

這道題是一道二分加最短路。

我們就二分答案，長度大于二分值就邊權為 1 1 1 ，長度小于等于二分值的就邊權為 0 0 0 。我們就跑一邊 spfa ，如果最短路的長度小于 k k k ，就可以，否則不可以。（因為多出來的 k k k 條可以免費）

代碼

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

struct node {
	int x, to, nxt;
}e[20001];
int n, p, k, KK, le[1001], x, y, z, l, r = 1000000, need[1001], ad, ans = -1;
bool in[1001], yes[1001];
queue<int>q;

void add(int x, int y, int z) {
	e[++KK] = (node){z, y, le[x]}; le[x] = KK;
	e[++KK] = (node){z, x, le[y]}; le[y] = KK;
}

bool work(int spend) {//最短路
	q.push(1);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
		for (int i = le[now]; i; i = e[i].nxt) {
			ad = 0;
			if (e[i].x > spend) ad = 1;//這個付不起，距離為1
			if (need[now] + ad < need[e[i].to]) {
				need[e[i].to] = need[now] + ad;
				if (!in[e[i].to]) {
					in[e[i].to] = 1;
					q.push(e[i].to);
				}
			}
		}
		
		in[now] = 0;
	}
	
	if (need[n] > k) return 0;
	return 1;
}

int main() {
	scanf("%d %d %d", &n, &p, &k);//讀入
	for (int i = 1; i <= p; i++) {
		scanf("%d %d %d", &x, &y, &z);
		add(x, y, z);//建圖
	}
	
	while (l <= r) {//二分
		memset(need, 0x7f, sizeof(need));//初始化
		need[1] = 0;
		in[1] = 1;
		
		int mid = (l + r) >> 1;
		if (work(mid)) {
			r = mid - 1;
			ans = mid;
		}
		else l = mid + 1;
	}
	
	printf("%d", ans);//輸出
	
	return 0;
}