最短路径?青蛙(Frogger), ZOJ1942, POJ2253

2017年07月24日 11点热度 0人点赞 0条评论

感觉只是用了最短路径的思想啊。

bellman算法是神奇的迭代,dijkstra是神奇的贪心。

看了下面这个图,感到这特么就是个最小生成树的计算过程啊。

最短路径?青蛙(Frogger), ZOJ1942, POJ2253

//本题求的是从起点到终点的所有通路中的最大的边的最小值(起点是第一个,终点是第二个坐标),感觉和最短路没有太大的关系,就是过程有点类似  
//请尽量选择c++编译器,g++神奇的wa 
#include
#include
#include
#include
#include
#include 
using namespace std;
const int mn=201,mm=40005;
struct Edge{
	int to,w,next;
}edges[mm];
int head[mn],n,tot,x[mn],y[mn];
inline int dist(int i,int j){
	return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
void add(int u,int v)
{//建双向边 
	edges[tot].to=v;
	edges[tot].w=dist(u,v);
	edges[tot].next=head[u];
	head[u]=tot++;
	
	edges[tot].to=u;
	edges[tot].w=dist(u,v);
	edges[tot].next=head[v];
	head[v]=tot++;
}
double spfa()
{
	queue q;
	int vis[mn]={1},dis[mn];
	//vis判断是否在队列中 
	for(int i=0;imax(dis[x],edges[j].w))
			{
				dis[v]=max(dis[x],edges[j].w);
				if(!vis[v])
				{
				vis[v]=1;
				q.push(v);
				 }
			}
		}
	}
	return sqrt(1.0*dis[1]);
}
int main(){
	int kase=1;
	while(scanf("%d",&n)&&n)
	{
		memset(head,-1,sizeof(head));
		tot=0;
		for(int i=0;i

//本题数据比较水,来个dfs,如果该点可以迭代,则以该点继续迭代下去,这个结论是对的,值得思考 
#include
#include
#include
#include
#include
#include
using namespace std;
const int mn=205,mm=40005;
struct Edge
{
    int to,w,next;
} edges[mm];
int head[mn],n,tot,x[mn],y[mn];
inline int dist(int i,int j)
{
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
void add(int u,int v)
{
    //建双向边
    edges[tot].to=v;
    edges[tot].w=dist(u,v);
    edges[tot].next=head[u];
    head[u]=tot++;

    edges[tot].to=u;
    edges[tot].w=dist(u,v);
    edges[tot].next=head[v];
    head[v]=tot++;
}
int d[mn],vis[mn];
void dfs(int i)
{
    for(int j=head[i]; ~j; j=edges[j].next)
    {
        int v=edges[j].to;
        if(d[v]>max(d[i],edges[j].w))
        {
        	d[v]=max(d[i],edges[j].w);
        	vis[v]=1;
			dfs(v);
			vis[v]=0;
		}
    }
}
int main()
{
    int kase=1;
    while(scanf("%d",&n)&&n)
    {
        memset(head,-1,sizeof(head));
        tot=0;
        for(int i=0; i

未经允许不得转载!最短路径?青蛙(Frogger), ZOJ1942, POJ2253

update

纸上得来终觉浅, 绝知此事须躬行。