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

1614: [Usaco2007 Jan]Telephone Lines架设电话线

news 来源：原创 2024/5/3 16:37:18

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1614

做法:二分答案

首先附上让我找了两天错的代码

#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct data{int to,next,c;}e[20001];
int n,p,k,cnt,head[1001],dis[1001],ans=-1;
bool vis[1001];
void insert(int u,int v,int w)
{cnt++;e[cnt].to=v;e[cnt].c=w;e[cnt].next=head[u];head[u]=cnt;}
bool spfa(int x)
{
    int sum,u,v;
    queue<int>q;
    q.push(1);
    memset(dis,127/3,sizeof(dis));
    dis[1]=0;
    while(!q.empty())
    {
        u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            v=e[i].c;
             if(e[i].c>x) sum=dis[u]+1;
             else sum=dis[u];
             if(dis[v]>sum)
             {
                dis[v]=sum;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
             }
        }
    }
    if(dis[n]<=x)
    return 1;
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&p,&k);
    for(int i=1;i<=p;i++)
    {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            insert(u,v,w);insert(v,u,w);
    }
    int l=0,r=1000000;
    while(l<=r)
    {
               int mid=(l+r)>>1;
               if(spfa(mid)){ans=mid;r=mid-1;}
               else l=mid+1;
               } 
    printf("%d",ans);
    return 0;
}

最后找到的是dis[n]<=k写成了dis[n]<=x

#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
struct data{int to,next,c;}e[20001];
int n,p,k,cnt,head[1001],dis[1001],ans=-1;
bool vis[1001];
void insert(int u,int v,int w)
{cnt++;e[cnt].to=v;e[cnt].c=w;e[cnt].next=head[u];head[u]=cnt;}
bool spfa(int x)
{
    int sum,u,v;
    queue<int>q;
    q.push(1);
    memset(dis,127/3,sizeof(dis));
    dis[1]=0;
    while(!q.empty())
    {
        u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            v=e[i].to;
             if(e[i].c>x) sum=dis[u]+1;
             else sum=dis[u];
             if(dis[v]>sum)
             {
                 dis[v]=sum;
                 if(!vis[v])
                 {
                     vis[v]=1;
                     q.push(v);
                 }
             }
        }
    }
    if(dis[n]<=k)
    return 1;
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&p,&k);
    for(int i=1;i<=p;i++)
    {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            insert(u,v,w);insert(v,u,w);
    }
    int l=0,r=1000000;
    while(l<=r)
    {
               int mid=(l+r)>>1;
               if(spfa(mid)){ans=mid;r=mid-1;}
               else l=mid+1;
               } 
    printf("%d",ans);
    return 0;
}