POJ 3662 Telephone Lines 二分答案+djk
/*POJ 3662 Telephone Lines题意：从1到N修一条电缆，有p对电线杆之间是可以连接的，电信公司可以提供k条电缆，其他的由John提供，求john提供的电缆的最长的那根的长度（ret）这应该有很多方案，但是还有一个条件，求所有方案中ret最小的那个所以应该让电信公司提供那k跟比较长的，剩下的那些有john提供，然后挑出最长的（长度L），也就是说只要是长度比L长的且在这条路上用到的电缆，那么就应该由电信公司提供。现在假设john提供的最长的电缆的长度是L，从1到N找出一条路来，使这条路上的长度比L大的电缆的个数不超过k（怎么算这个个数？长度大于L的电缆的边权1，john提供的电缆的边权0，然后求最短路就是），那个这就是一个方案，只需尽量的使L小就可以了（二分长度即可求 一个最佳值）*/#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct edge{int a,b,l;}bian[10100];int map[1010][1010];int vis[1010];int dist[1010];int inf=0x7ffffff;bool cmp(struct edge a,struct edge b){return a.l<b.l;}void build(int l,int n,int p){int i,j;for(i=0;i<=n;++i){for(j=0;j<=n;++j){map[i][j]=inf;}}for(i=0;i<p;++i){int a,b;a=bian[i].a;b=bian[i].b;if(bian[i].l<=l){map[a][b]=map[b][a]=0;}else map[a][b]=map[b][a]=1;}}int xun(int n)//在剩余的节点中寻找到1最近的 { int xia=-1,i; for(i=1;i<=n;i++) if(vis[i]==0&&(xia==-1||dist[i]<dist[xia])) xia=i; return xia; } int djk(int n) { int i,j,just; for(i=1;i<=n;i++)//初始化 dist[i]=map[1][i]; memset(vis,0,sizeof(vis)); vis[1]=1; for(i=2;i<=n;i++) { just=xun(n); vis[just]=1;//just最近，将他标为已找到最短路径 for(j=1;j<=n;j++)//更新剩余的 if(vis[j]==0&&dist[j]>dist[just]+map[just][j]) dist[j]=dist[just]+map[just][j]; } return dist[n];} int bin(int n,int p,int k){int head,tail;head=0;tail=p-1;int mid;while(head<=tail) { int mid=(head+tail)>>1; build(bian[mid].l,n,p); if(djk(n)<=k)//求出最小的 { tail=mid-1; }else head=mid+1;}return head;}int main(){int i,n,p,k;while(scanf("%d%d%d",&n,&p,&k)!=EOF){for(i=0;i<p;i++){scanf("%d%d%d",&bian[i].a,&bian[i].b,&bian[i].l);}sort(bian,bian+p,cmp);build(0,n,p);int duan=djk(n);if(duan==inf){printf("-1\n");}else{if(duan<=k)printf("0\n");else printf("%d\n",bian[bin(n,p,k)].l);}}return 0;}