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

题目链接

题目大意：给定一张图，定义两点间的距离为路径上边权的max，
可以使k条边边权为0，求1~n的最短路

题解：分层图？不需要，贪心考虑，免费道路一定选权大的
二分答案，判断能否找到一条路径，使得该路径上大于mid的值不超过k条，将大于mid的边权置为1，否则为0，最短路即可求解

我的收获：贪心考虑，大力二分

#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
const int M=10005;
int m,n,x,y,z,t,w,r,l,mid,ans=-1,c;
int head[M],d[M],p[M];
bool vis[M],mark[M];
queue <int> q;struct edge{int from,to,next,val;
}e[M*10];void ready(int s)
{for(int i=1;i<=n;i++)d[i]=INF,vis[i]=0;d[s]=0;vis[s]=1;
}void add(int i,int j,int v)
{e[t].from=i;e[t].to=j;e[t].val=v;e[t].next=head[i];head[i]=t++;
}inline void spfa(int s,int mx)
{ready(s);q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(e[i].val>mx) c=1;else c=0;if(d[v]>d[u]+c){d[v]=d[u]+c;if(!vis[v]){q.push(v);vis[v]=1;}}}}
}
bool ok(int x)
{spfa(1,x);return d[n]<=w;
}
void work()
{l=0;r=INF;while(l<=r){mid=(l+r)>>1;if(ok(mid)) r=mid-1,ans=mid;else l=mid+1;}printf("%d\n",ans);
}
void init()
{memset(head,-1,sizeof(head));cin>>n>>m>>w;while(m--){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}
}
int main()
{init();work();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！