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;
}