首页 > 代码库 > BZOJ 1682: [Usaco2005 Mar]Out of Hay 干草危机
BZOJ 1682: [Usaco2005 Mar]Out of Hay 干草危机
Description
牛们干草要用完了！贝茜打算去勘查灾情．
有N(2≤N≤2000)个农场，M(≤M≤10000)条双向道路连接着它们，长度不超过10^9．每一个农场均与农场1连通．贝茜要走遍每一个农场．她每走一单位长的路，就要消耗一单位的水．从一个农场走到另一个农场，她就要带上数量上等于路长的水．请帮她确定最小的水箱容量．也就是说，确定某一种方案，使走遍所有农场通过的最长道路的长度最小，必要时她可以走回头路．
Input
第1行输入两个整数N和M;接下来M行，每行输入三个整数，表示一条道路的起点终点和长度．
Output
输出一个整数，表示在路线上最长道路的最小值．
题解：
Djk求从1到每个点，路径上最大边的最小值，取max即可。
代码：
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<queue>//by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);int H[2005],X[20005],P[20005];LL E[20005];LL d[2005];int tot;inline void add(int x,int y,LL z){ P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;}int n,m;int x,y;LL z;struct N{ int x; LL w; N(int a=0,int b=0){ x=a,w=b; } friend bool operator < (N a,N b){ return a.w>b.w; }};priority_queue<N> q;bool vis[2005];int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d%d",&n,&m); memset(d,0x3f,sizeof d); for(int i=0;i<m;i++){ scanf("%d%d%lld",&x,&y,&z); add(x,y,z); add(y,x,z); } d[1]=0; q.push(N(1,0)); while(!q.empty()){ x=q.top().x;q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=H[x];i;i=X[i]){ if(d[P[i]]>max(d[x],E[i])){ d[P[i]]=max(d[x],E[i]); q.push(N(P[i],d[P[i]])); } } } LL ans=0; for(int i=2;i<=n;i++) ans=max(ans,d[i]); printf("%lld\n",ans); return 0;}
BZOJ 1682: [Usaco2005 Mar]Out of Hay 干草危机
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。