首页 > 代码库 > 二分+最短路
二分+最短路
二分+最短路
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu
Description
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(1<=p<=10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。
第i对电线杆的两个端点分别是ai,bi，它们的距离为li(1<=li<=1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号N的电话线杆上。也就是说，笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。
电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对，那么支出为0.
请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？
Input
输入文件的第一行包含三个数字n,p,k;
第二行到第p+1行，每行分别都为三个整数ai,bi,li。
Output
一个整数，表示该项工程的最小支出，如果不可能完成则输出-1.
Sample Input
5 7 11 2 53 1 42 4 83 2 35 2 93 4 74 5 6Sample Output
4
//挺有意思的一道题，要使第 k+1 边的值越小越好。想不到啊，spfa还能这么用，二分还能这么用
79ms
1 #include <stdio.h> 2 #include <string.h> 3 4 #define MAXN 1005 5 6 struct Edge{ 7 int v,w; 8 int next; 9 }edge[30005];10 int headlist[MAXN];11 12 int n,p,k,bian=0;13 14 void join(int a,int b,int c)15 {16 bian++;17 edge[bian].v=b;18 edge[bian].w=c;19 edge[bian].next=headlist[a];20 headlist[a]=bian;21 }22 23 int Q[1000];24 int vis[MAXN];25 int dis[MAXN];//大于limit的最少有多少个26 int spfa(int limit)27 {28 for (int i=1;i<=n;i++)29 dis[i]=10000000;//kanknkkkkkkkkkkkkk30 memset(vis,0,sizeof(vis));31 32 Q[0]=1;33 int l=0,r=1;34 dis[1]=0,vis[1]=1;35 while (l!=r)36 {37 int now=Q[l++];38 if (l==1000) l=0;39 vis[now]=0;40 int i=headlist[now];41 int mm=dis[now];42 while (i)43 {44 if (edge[i].w>limit) mm=dis[now]+1;45 else mm=dis[now];46 if (mm<dis[edge[i].v])47 {48 dis[edge[i].v]=mm;49 if (vis[edge[i].v]==0)50 {51 Q[r++]=edge[i].v;52 if (r==1000) r=0;53 vis[edge[i].v]=1;54 }55 }56 i=edge[i].next;57 }58 }59 if (dis[n]<=k) return 1;//60 return 0;61 }62 63 int main()64 {65 scanf("%d%d%d",&n,&p,&k);66 int a,b,c;67 for (int i=1;i<=p;i++)68 {69 scanf("%d%d%d",&a,&b,&c);70 join(a,b,c);71 join(b,a,c);72 }73 int l=0,r=1000000,ans=-1;74 while (l<=r)75 {76 int mid=(l+r)/2;77 if (spfa(mid))78 {79 ans=mid;//记录后，看能不能有更小的值符合条件80 r=mid-1;81 }82 else l=mid+1;//不能的话，只能看有没更大的了83 }84 printf("%d\n",ans);85 return 0;86 }
二分+最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。