我用的spfa,80
by Yumeng_Xue @ 2015-10-24 22:47:44
很抱歉，开始没看见。
能不能把您的程序发一下?
我始终没查出来我的哪里错了.
by cyy489 @ 2015-10-24 23:05:35
同求@[url=/space/show?uid=393]xym6336[/url]
by zzjzxh @ 2015-10-25 07:09:52
我感觉SPFA是可以的。。但是我的Wa3个T1个。。求出一个点到其他所有点所经过路径最大高度差最小的值，而这些最小值中最大的就是答案。
by Skyo @ 2015-10-25 07:28:11
我感觉SPFA是可以的。。但是我的Wa3个T1个。。求出一个点到其他所有点所经过路径最大高度差最小的值，而这些最小值中最大的就是答案。
by Skyo @ 2015-10-25 07:28:42
表示被卡tle一个点，要程序的话私信我
by loidc @ 2015-10-25 07:31:51
Dijkstra吧
spfa稠密图容易被卡
by nlj1999 @ 2015-10-25 12:59:09
@[url=/space/show?uid=9763]cyy489[/url] @[url=/space/show?uid=3882]zzjzxh[/url]
写的很渣，轻喷 wa了一个t了一个，不知道怎么wa的
[codec ]
```cpp
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int m,n,h[260000];
bool lb[510][510],vis[260000];
int d[260000];
queue<int> q;
void spfa(int num)
{
memset(d,-1,sizeof(d));
d[num]=0;
vis[num]=true;
q.push(num);
int u;
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=false;
if((u-n>0) && (d[u-n]==-1 || d[u-n]>max(d[u],abs(h[u-n]-h[u]))))
{
d[u-n]=max(d[u],abs(h[u-n]-h[u]));
if(!vis[u-n])
{
vis[u-n]=true;
q.push(u-n);
}
}
if((u+n<=m*n) && (d[u+n]==-1 || d[u+n]>max(d[u],abs(h[u+n]-h[u]))))
{
d[u+n]=max(d[u],abs(h[u+n]-h[u]));
if(!vis[u+n])
{
vis[u+n]=true;
q.push(u+n);
}
}
if((u%n-1>0) && (d[u-1]==-1 || d[u-1]>max(d[u],abs(h[u-1]-h[u]))))
{
d[u-1]=max(d[u],abs(h[u-1]-h[u]));
if(!vis[u-1])
{
vis[u-1]=true;
q.push(u-1);
}
}
if((u%n+1<=n) && (d[u+1]==-1 || d[u+1]>max(d[u],abs(h[u+1]-h[u]))))
{
d[u+1]=max(d[u],abs(h[u+1]-h[u]));
if(!vis[u+1])
{
vis[u+1]=true;
q.push(u+1);
}
}
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
scanf("%d",&h[(i-1)*n+j]);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
scanf("%d",&lb[i][j]);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
if(lb[i][j])
{
spfa((i-1)*n+j);
goto lab;
}
```
lab:
```cpp
int max=0;
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
if(lb[i][j] && d[(i-1)*n+j]>max)
max=d[(i-1)*n+j];
printf("%d",max);
return 0;
}
[/codec ]
```
by Yumeng_Xue @ 2015-10-25 22:49:47
这个不是二分吗。。。。跟spfa有什么关系。。。
by Vic_ @ 2017-02-25 11:19:53
4\*n的边不算稠密图吧@ nlj1999
by tlyangwj @ 2017-11-02 23:08:35