首页 > 代码库 > 1614: [Usaco2007 Jan]Telephone Lines架设电话线
1614: [Usaco2007 Jan]Telephone Lines架设电话线
传送门：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; }
Carrot阿,你真的要反思一下，为什么会做的题目拿不到分，因为你总是不在意这些细节，，，但是没有细节你什么都不是。
1614: [Usaco2007 Jan]Telephone Lines架设电话线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。