`
huyifan951124
  • 浏览: 82767 次
社区版块
存档分类
最新评论

Poj2253 dijkstra最短路变形

阅读更多

题意:求1点到2点的所有能够到2点的所有通路里的的最大路径(这里的路径特指两点之间的线段)的最小值。

这题对我来说收获颇丰,我们可以修改dijkstra里面的松弛函数,使得其变为求每个点的满足条件的值,并用dist数组来记录。详见代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define INF2 -0x3f3f3f3f
typedef struct Node
{
    double x;
    double y;
};
Node nodes[205*2];
typedef struct Egde
{
    int l;
    int r;
    double value;
};
double a[205*2][205*2];
double dist[205*2];
bool visited[205*2];
int n,sx,sy,ex,ey;
double Max;
void dijkstra()
{

    visited[1]=true;
    for(int i=1; i<=n; i++)
    {
        dist[i]=a[1][i];
    }
    for(int i=1; i<=n; i++)
    {
         int Min=INF,node=0;
        for(int j=1; j<=n; j++)
        {
            if(!visited[j]&&Min>dist[j])
            {
                Min=dist[j];
                node=j;
            }
        }
        if(node==0)
            return;
        visited[node]=true;


        for(int j=1; j<=n; j++)
        {

            Max=max(dist[node],a[node][j]);//构成dist[node]和a[node][j]里找最大的边,因为这两条边来构成一条新的dist[j]
            //用为要去最大边里的最小边,那么我们就要把它和原来的dist[j]进行比较
            //再把较小的边赋给dist[j]来成为新的dist[j]以便进行下次更新            dist[j]=min(dist[j],Max);
            dist[j]=min(dist[j],Max);
        }
    }


}
int main()
{
    int sym=0;
    while(scanf("%d",&n)&&n!=0)
    {
        sym++;
        memset(nodes,0,sizeof(nodes));
        memset(a,0x3f,sizeof(a));
        memset(dist,0x3f,sizeof(dist));
        memset(visited,false,sizeof(visited));
        for(int i=1; i<=n; i++)
        {
            scanf("%lf%lf",&nodes[i].x,&nodes[i].y);
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                double d=sqrt((nodes[i].x-nodes[j].x)*(nodes[i].x-nodes[j].x)+(nodes[i].y-nodes[j].y)*(nodes[i].y-nodes[j].y));
                a[i][j]=a[j][i]=d;
                a[i][i]=0;
            }
        }

        Max=INF;
        dijkstra();
        printf("Scenario #%d\n",sym);
        printf("Frog Distance = %.3f\n\n",dist[2]);
    }


    return 0;

}


 

 

分享到:
评论

相关推荐

    POJ2253-Frogger【Floyd】

    标题中的"POJ2253-Frogger【Floyd】"是指北京大学在线编程平台POJ(Problem Set)上的第2253题——“Frogger”,这是一道编程题目,通常涉及到算法和逻辑思维。Floyd在这里指的是弗洛伊德算法,它可能在这道题的解决...

    poj 2387 dijkstra

    dijkstra 算法 需要考虑重边.........

    POJ1062-Expensive dowry【dijkstra】

    【标题】"POJ1062-Expensive dowry【dijkstra】"涉及的问题是图论中的一个重要算法——Dijkstra算法,这是一个用于求解单源最短路径问题的算法,通常在计算机科学和信息技术领域有广泛应用,如路由选择、网络优化等...

    poj题目分类

    * 最短路径算法:例如 Dijkstra、Bellman-Ford、Floyd、Heap+Dijkstra,例如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、...

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    poj训练计划.doc

    - 最短路径算法:如Dijkstra算法和Bellman-Ford算法,用于找到两点间的最短路径,如`poj1062, poj2253`。 - 最小生成树算法:如Prim算法和Kruskal算法,用于找出图中的最小生成树,如`poj1789, poj2485`。 - 拓扑...

    POJ2009年最新版

    POJ2009年最新版,相当详细.................

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    acm训练计划(poj的题)

    - (poj1860, poj3259, poj1062, poj2253, poj1125, poj2240):介绍迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)、弗洛伊德算法(Floyd)等。 - 使用堆优化的迪杰斯特拉算法。 3. **最小生成树...

    POJ3295-Tautology

    解题者可能使用了栈来存储运算符和操作数,逐步处理逻辑表达式,或者采用了类似Dijkstra的短路评估法来简化表达式并判断其真伪。 在解题报告中,可能会详细解释如何将逻辑表达式转换为后缀表达式,如何利用栈来执行...

    poj各种分类

    Dijkstra算法、Bellman-Ford算法和Floyd算法分别适用于无负权边、有负权边和所有类型的加权图,而Heap-Dijkstra结合了Dijkstra算法与堆优化,提高了解决大规模图问题的效率。 #### 最小生成树 Prim算法和Kruskal...

    POJ题目简单分类(ACM)

    - **最短路径算法**:包括dijkstra、bellman-ford、floyd和heap+dijkstra,如poj1860等,用于找到节点间的最短距离。 - **最小生成树算法**:prim和kruskal算法,如poj1789,用于找到图的最小成本连接。 - **拓扑...

    经典 的POJ 分类

    - POJ 1062、POJ 2253:涉及Bellman-Ford算法的应用场景。 - POJ 1125、POJ 2240:Floyd算法的典型实例。 ##### 最小生成树 - **算法**: - Prim算法 - Kruskal算法 - **题目示例**: - POJ 1789、POJ 2485:...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    acm新手刷题攻略之poj

    ### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...

    POJ 分类题目 txt文件

    从给定的文件信息来看,这是一份关于POJ(Pat Online Judge)平台上的编程题目的分类汇总。POJ是北京大学设立的一个在线编程评测系统,提供了大量的编程题目供学习者练习,涵盖了各种算法和数据结构知识。下面将对这...

    poj图论题目汇总

    #### 2267 *From Dusk till Dawn or: Vladimir the Vampire - 最短路 - **知识点**:最短路径算法。 #### 2289 Jamie's Contact Groups - 网络流 - **知识点**:网络流算法。 #### 2337 Catenyms - 欧拉通路 - ...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

Global site tag (gtag.js) - Google Analytics