# POJ 3662 Telephone Lines（二分答案+SPFA）

【题目大意】

给出点，给出两点之间连线的长度，有k次免费连线，

要求从起点连到终点，所用的费用为免费连线外的最长的长度。

求最小费用。

【题解】

二分答案，对于大于二分答案的边权置为1，小于等于的置为0，
则最短路就是超出二分答案的线数，如果小于等于k，则答案是合法的

【代码】

```#include <cstdio>
#include <cstring>
using namespace std;
const int N=200010,inf=~0U>>2,M=200000;
int ans=-1,x,S,T,time[N],q[N],size,h,t,n,m,k,ed,dis[N],in[N],nxt[N],w[N],v[N],g[N],u,e,cost;
void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
bool spfa(int S,int limit){
for(int i=1;i<=n;i++)dis[i]=inf,in[i]=0,time[i]=0;
time[S]=1,dis[S]=0,in[S]=1;
int i,x,size; q[h=t=size=1]=S;
while(size){
for(i=g[x=q[h]],h=(h+1)%M,size--;i;i=nxt[i])if(dis[x]+(w[i]>limit?1:0)<dis[v[i]]){
dis[v[i]]=dis[x]+(w[i]>limit?1:0);
if(!in[v[i]]){
time[v[i]]++,t=(t+1)%M,size++,in[q[t]=v[i]]=1;
if(time[v[i]]>n)return 0;
}
}in[x]=0;
}return dis[T]<=k;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt));
memset(w,0,sizeof(w)); memset(g,0,sizeof(g)); ed=0;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&e,&cost);
add(u,e,cost);add(e,u,cost);
}int l=0,r=1000000;T=n;
while(l<=r){
int mid=(l+r)>>1;
if(spfa(1,mid)){ans=mid;r=mid-1;}
else l=mid+1;
}return printf("%d\n",ans),0;
}
```

## POJ 3662 Telephone Lines【Dijkstra最短路+二分求解】

Telephone Lines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7214   Accepted: 2638 Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of

## poj 3662 Telephone Lines（最短路+二分）

Telephone Lines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6973   Accepted: 2554 Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of

## POJ 3662 Telephone Lines （分层图）

Telephone Lines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6785   Accepted: 2498 Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of

## poj 3662 Telephone Lines dijkstra+二分搜索

Telephone Lines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5696   Accepted: 2071 Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of

## POJ 3662 Telephone Lines （分层图做法）

Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. There are N (1 ≤ N ≤ 1,000) forlorn t

## poj 3662 Telephone Lines（好题！！！二分搜索+dijkstra）

Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. There are N (1 ≤ N ≤ 1,000) forlorn t