Description
Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。 经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过 K对，那么FJ的总支出为0。 请你计算一下，FJ最少需要在电话线上花多少钱。
Input
* 第1行: 3个用空格隔开的整数：N，P，以及K
* 第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i
Output
* 第1行: 输出1个整数，为FJ在这项工程上的最小支出。如果任务不可能完成， 输出-1
Sample Input
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输入说明:
一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话
线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信
公司可以免费为FJ连结一对电话线杆。
Sample Output
输出说明:
FJ选择如下的连结方案：1->3；3->2；2->5，这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线，于是，
他所需要购买的电话线的最大长度为4。
HINT
Source
Silver
Solution
可以二分一下最大长度，然后跑一遍最短路来判断是否可行。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<iostream> #include<cstdio> using namespace std; const int N=1005,M=10005; int n,m,k,tot,Next[M<<1],head[N],tree[M<<1],val[M<<1],dis[N],x[N<<1]; bool visit[N]; void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } int spfa(int X) { for (int i=1;i<=n;i++) dis[i]=1<<29,visit[i]=false; x[1]=1;dis[1]=0;visit[1]=true; int t=0,w=1; while (t!=w) { int u=x[++t]; if (t>n*2) t=1; visit[u]=false; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (dis[u]+((val[i]>X)?1:0)<dis[v]) { dis[v]=dis[u]+((val[i]>X)?1:0); if (!visit[v]) { x[++w]=v; if (w>n*2) w=1; visit[v]=true; } } } } return dis[n]; } bool check(int x) { if (spfa(x)<=k) return true; return false; } int main() { scanf("%d%d%d",&n,&m,&k); tot=0; int x,y,z; for (int i=1;i<=m;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); int l=0,r=1000001; while (l<r) { int mid=(l+r)/2; if (check(mid)) r=mid;else l=mid+1; } if (r==1000001) puts("-1");else printf("%d\n",r); return 0; } |
