首页 > 代码库 > BZOJ 1614: [Usaco2007 Jan]Telephone Lines
BZOJ 1614: [Usaco2007 Jan]Telephone Lines
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1614
解:首先我们先用一次dijkstra来判断出特殊情况,比如说路不联通,或者说所需连的电线数小于等于提供的电线数。
然后,我们二分我们所需支付的那根最长的电线长度x,再做一遍dijkstra(当然spfa更好啦),如果过程中有访问到
比x长的电线,就给距离+1,表示这段路上需要提供多少免费连接的电线,这样最短路就是,当我们支付x元的时候,
至少要有多少免费提供的电线,如果可以提供这么多的话,就更新答案,说明我们付x元就够了。
程序:
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define maxn 2100000000 using namespace std; struct ding{ int to,next,val; }edge[40000]; bool vis[40000]; int ans=maxn,head[4000],cnt,n,p,k,dis[40000],w[40000]; void add(int u,int v,int op) { edge[++cnt].to=v; edge[cnt].val=op; edge[cnt].next=head[u]; head[u]=cnt; } void dijkstra(int x) { dis[1]=0; for (int i=2;i<=n;i++) dis[i]=maxn; for (int i=1;i<=n;i++) vis[i]=false; for (int tot=1;tot<=n;tot++) { int minx=maxn; int ch=0; for (int i=1;i<=n;i++) if ((!vis[i])&&(dis[i]<minx)) { minx=dis[i]; ch=i; } if ((ch==0)||(ch==n)) break; vis[ch]=true; for (int i=head[ch];i;i=edge[i].next) { int y=edge[i].to; if (edge[i].val<=x) dis[y]=min(dis[y],dis[ch]); else dis[y]=min(dis[y],dis[ch]+1); } } } int check(int x) { dijkstra(x); if (dis[n]<=k) return true; else return false; } void dijkstra1() { for (int i=2;i<=n;i++) dis[i]=maxn; dis[1]=0; for (int tot=1;tot<=n;tot++) { int minx=maxn; int ch=0; for (int i=1;i<=n;i++) if ((!vis[i])&&(dis[i]<minx)) { minx=dis[i]; ch=i; } if ((ch==0)||(ch==n)) break; vis[ch]=true; for (int i=head[ch];i;i=edge[i].next) { int y=edge[i].to; if (!vis[y]) dis[y]=min(dis[y],dis[ch]+1); } } } int main() { scanf("%d%d%d",&n,&p,&k); int a,b; for (int i=1;i<=p;i++) { scanf("%d%d%d",&a,&b,&w[i]); add(a,b,w[i]); add(b,a,w[i]); } dijkstra1(); if (dis[n]<=k) {printf("0\n");return 0;} else if (dis[n]==maxn) {printf("-1\n");return 0;} sort(w+1,w+1+p); int l=1,r=p; while (l<=r) { int mid=(l+r)/2; if (check(w[mid])) { ans=min(ans,w[mid]); r=mid-1; } else l=mid+1; } printf("%d\n",ans); return 0; }
BZOJ 1614: [Usaco2007 Jan]Telephone Lines
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。