当前位置：首页 > news >正文

poj 3662 Telephone Lines (二分+最短路径)

news 来源：原创 2024/5/14 17:30:09

  1 
http://poj.org/problem?id=3662
/*
  2 二分+最短路径
  3 题意：求解额外付出的最小的最大边,k段是免费的.
  4 
  5 题目的关键在于枚举最小的最大边，如何枚举呢？用二分法，选一条边，重新构图；
  6 在图中大于这条边的，记为1；
  7 把小于等于这条边的 边记为0；
  8 求 1-》n的最短距离len
  9 
 10 题目有3种情况,
 11 
 12 1 不连通的情况
 13 
 14 2 不需要额外花费的情
 15 3  需要花费（那么了一定存在一个边 使   len==k）
 16 */
 17 #include<cstdio>
 18 #include<algorithm>
 19 #define inf 0x7fffffff
 20 #define maxn 2000
 21 using namespace std;
 22 int n,p,k;
 23 int map[maxn][maxn],dis[maxn],vis[maxn];
 24 struct node
 25 {
 26     int a;
 27     int b;
 28     int w;
 29 }edge[maxn*10];
 30 int cmp(const node &A,const node &B)
 31 {
 32     return A.w<B.w;
 33 }
 34 void inite(int x)//重新构图
 35 {
 36     int i,j;
 37     for(i=0;i<=n;i++)
 38     {
 39         for(j=0;j<=n;j++)
 40           {
 41 
 42              map[i][j]=inf;
 43 
 44           }
 45     }
 46     for(i=0;i<p;i++)
 47     {
 48         int a=edge[i].a;
 49         int b=edge[i].b;
 50         int len=edge[i].w;
 51         if(len<=x)
 52         {
 53             map[a][b]=map[b][a]=0;
 54         }
 55         else map[a][b]=map[b][a]=1;
 56     }
 57 }
 58 int djk()
 59 {
 60     int i,j,min,key;
 61 
 62     for(i=1;i<=n;i++)
 63     {
 64       dis[i]=map[1][i];
 65       vis[i]=0;
 66     }
 67     dis[1]=0;
 68     vis[1]=1;
 69     for(i=1;i<=n-1;i++)
 70     {
 71         min=inf;
 72         for(j=1;j<=n;j++)
 73         {
 74             if(!vis[j]&&dis[j]<min)
 75             {
 76                 min=dis[j];
 77                 key=j;
 78             }
 79         }
 80         vis[key]=1;
 81         for(j=1;j<=n;j++)
 82         {
 83             if(!vis[j]&&map[key][j]!=inf&&dis[j]>dis[key]+map[key][j])
 84             dis[j]=dis[key]+map[key][j];
 85         }
 86     }
 87     return dis[n];
 88 }
 89 int bin()//二分枚举最小的最大边
 90 {
 91     int head=0,tail=p-1;
 92     while(head<=tail)
 93     {
 94         int mid=(head+tail)>>1;
 95         inite(edge[mid].w);
 96         if(djk()<=k)//求出最小的
 97         {
 98             tail=mid-1;
 99         }
100         else head=mid+1;
101     }
102     return head;
103 }
104 int main()
105 {
106     int i;
107     while(scanf("%d%d%d",&n,&p,&k)!=EOF)
108     {
109         for(i=0;i<p;i++)
110         {
111             scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].w);
112         }
113         sort(edge,edge+p,cmp);
114         inite(0);
115         int f=djk();
116         if(f==inf)printf("-1\n");
117         else
118         {
119             if(f<=k)printf("0\n");
120             else  printf("%d\n",edge[bin()].w);
121         }
122     }
123 
124 }