[cpp] /* 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; }
