电话网络

问题描述

由于地震使得连接汶川县城电话线全部损坏，假如你是负责将电话线接到震中汶川县城的负责人，汶川县城周围分布着N(1≤N≤1,000)根按 1..N 顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1≤P≤10,000)对电话线杆间可以拉电话线，其余的由于地震使得无法被连接。
第i对电话线杆的两个端点分别为Ai，Bi，它们间的距离为Li(1≤Li≤1,000,000)。数据中保证每对(Ai，Bi)最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个县城的电话线全都连到了编号为N的电话线杆上。也就是说，你的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。电信公司决定支援灾区免费为汶川县城连结K(0≤K<N)对由你指定的电话线杆。对于此外的那些电话线，需要为它们付费，总费用等于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过K对，那么总支出为0。
请你计算一下，将电话线引到震中汶川县城最少需要在电话线上花多少钱?

输入格式

第一行包含三个用空格隔开的整数：N，P和K。
第二行到第P+1行：每行分别都为空格隔开的整数：Ai，Bi和Li。

输出格式

仅包含一个整数，表示在这项工程上的最小支出。如果任务不可能完成，则输出-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

样例输出

题解

为了花费最少，免费的电话线杆要尽可能多，当K对电话线杆都用完之后，最长的电话线越短越好

即，求一条从1到n的路径，使得这条路径上第K+1长的路最短

考虑二分总花费mid，即需要付钱的最长的电话线，那么所有长度大于mid的电话线都视为免费，用最短路求从1到n需要的最少的免费的电话线数，若大于K，说明当前二分的mid过小，反之，则当前mid满足条件且可能更大

 1 #include <cstring>
 2 #include <cstdio>
 3 const int maxn=1005;
 4 int n,m,K,fir[1005],num,dis[1005],q[1005];
 5 bool vis[1005];
 6 struct node{
 7     int u,w,nex;
 8 }g[20005];
 9 void add(int x,int y,int z)
10 {
11     g[++num].u=y;       g[num].w=z;
12     g[num].nex=fir[x];  fir[x]=num;
13 }
14 void spfa(int mid)
15 {
16     int u,v,k,h,t;
17     memset(dis,63,sizeof(dis));
18    // printf("%d
",dis[0]);
19     memset(vis,0,sizeof(vis));
20     dis[1]=0;
21     h=0;  t=1;  q[1]=1;  vis[1]=1;
22     while (h!=t)
23     {
24         (++h)%=maxn;
25         u=q[h];  vis[u]=0;
26         for (k=fir[u];k;k=g[k].nex)
27         {
28             v=g[k].u;
29             if (dis[v]>dis[u]+(g[k].w>mid))
30             {
31                 dis[v]=dis[u]+(g[k].w>mid);
32                 if (!vis[v])
33                 {
34                     vis[v]=1;
35                     if (dis[v]<dis[q[(h+1)%maxn]])
36                       q[h]=v,h=(h-1+maxn)%maxn;
37                     else (++t)%=maxn,q[t]=v;
38                 }
39             }
40         }
41     }
42     return;
43 }
44 int main()
45 {
46     int i,j,x,y,z;
47     scanf("%d%d%d",&n,&m,&K);
48     for (i=1;i<=m;i++)
49       scanf("%d%d%d",&x,&y,&z),
50       add(x,y,z),add(y,x,z);
51     int l=0,r=1e6,mid,ans=-1;
52     while (l<=r)
53     {
54         mid=(l+r)>>1;
55         spfa(mid);
56         if (dis[n]<=K) ans=mid,r=mid-1;
57         else l=mid+1;
58     }
59     printf("%d",ans);
60     return 0;
61 }