`
xinjiang
  • 浏览: 55707 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

POJ Frogger--Dijkstra算法

阅读更多

 

Description


一只叫Freddy的青蛙蹲坐在湖中的一块石头上。突然他发现一只叫Fiona的青蛙在湖中的另一块石头上。Freddy想要跟Fiona约会,但由于湖水太脏,他不想游泳过去而是跳过去找Fiona。
很不幸,Fiona所在的石头距离他有点远,甚至超出了他的跳跃能力。然而Freddy注意到湖中还有一些其他的石头。这些石头也许会将这个很长的跳跃距离化成若干个短的跳跃距离。
我们定义“青蛙距离”为Freddy跳到Fiona那里所需要的若干次跳跃中最长的那一次。现在给你Freddy,Fiona,以及湖中其他石头的坐标,让你求出最短的“青蛙距离”。

Input


输入有可能是多组测试数据。每组数据的第一行有一个整数n(2<=n<=200),表示湖中一共有多少块石头。接下来的n行,每一行有两个整数xi,yi(0 <= xi,yi <= 1000),表示第i块石头的坐标。第1块石头的坐标是Freddy所在的位置,第二块石头的坐标是Fiona所在的位置,其他的石头上都没有青蛙。当输入n=0的时候,程序结束。

Output


对于每一组测试数据,先输出一行"Scenario #x",然后在下一行输出"Frog Distance = y"。其中x表示当前是第几组测试数据,y为该组数据的最小“青蛙距离”。每两组测试数据之间输出一个空行。

Sample Input

2
0 0
3 4

3
17 4
19 4
18 5

0

Sample Output

Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414
这个题目的意思太难理解了,我开始还以为是从第一个点到第二个点之间的最短距离,可结果错了。原来是求从第
一个节点到第二个节点的生成的最小二叉树中的最大长度。好了不罗嗦了,直接看代码吧!
#include <stdio.h>
#include <string.h>
#include <math.h>

#define INFINITE 999999999.9
#define N 201


double getLength(double x1, double y1, double x2, double y2)
{
    /*求两点之间的距离*/
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}


double Dijkstra(double map[N][N], int v, int n, int m)
{
    int i;
    int s[N];         //s[i]=0代表顶点未入S集,s[i]=1表示顶点i已入S集
    double dist[N];   //dist[i]表示当前已知的从源点到顶点i的最短路径的长度
    double min, max;
    int u;


    for(i = 0; i < n; i++)
    {
        dist[i] = map[v][i];
        s[i] = 0;
    }

    s[v] = 1;    //初始时v进入s集
    dist[v] = 0;
    max = 0;
    u = v;

    while(u != m)
    {
        min = INFINITE;
        for(i = 0; i < n; i++)   //求源点u到其他顶点i的最短距离
        {
            if(!s[i] && (dist[i] < min))
            {
                u = i;
                min = dist[i];
            }
        }

        if(min > max)  max = min;
        s[u] = 1;   //将u加入s集

        for(i = 0; i < n; i++)
        {
            if(!s[i] && (map[u][i] < INFINITE) && (map[u][i] < dist[i]))
            {
                dist[i] = map[u][i];
            }
        }
    }

    return max;
}


int main()
{
    int i, j, k;
    int n, count = 0;
    double map[N][N];
    int x[N], y[N];

    while(scanf("%d", &n) && n)
    {
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < n; j++)
            {
                map[i][j] = INFINITE;
            }
            scanf("%d %d", &x[i], &y[i]);
        }

        for(i = 0; i < n; i++)
        {
            /*建图*/
            for(j = 0; j < n; j++)
            {
                map[i][j] = getLength(x[i], y[i], x[j], y[j]);
            }
        }

        printf("Scenario #%d\n", ++count);
        printf("Frog Distance = %.3lf\n\n", Dijkstra(map, 0, n, 1));
    }
    return 0;
}
 

 

分享到:
评论

相关推荐

    POJ2002-Squares

    总的来说,"POJ2002-Squares"是一个结合了数学、算法和编程实践的学习资源,对于提升编程技能和解决问题的能力非常有帮助。通过深入研究解题报告和AC代码,可以学习到如何有效地处理和求解这类问题,从而在未来的...

    POJ3253-POJ3253-Fence Repair【STL优先队列】

    标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...

    POJ1062-Expensive dowry【dijkstra】

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

    POJ1426-Find The Multiple【BFS+同余模】

    【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...

    POJ2253-Frogger【Floyd】

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

    POJ1129-Channel Allocation【四色定理】

    3. "POJ1129-Channel Allocation.doc":这可能是一个Word文档,包含了详细的解题报告,包括问题分析、算法设计、代码实现和可能的优化策略。 在这个题目中,参赛者可能需要将一个网络中的电台(或频道)分配到有限...

    POJ3020-Antenna Placement

    2. "POJ3020-Antenna Placement.doc":这可能是一个Word文档,详细记录了解题过程、思路分析、算法描述以及可能的复杂度分析。文档通常包括了问题的输入输出格式、限制条件、样例测试等关键信息。 从题目“Antenna ...

    poj 1000 - 2000 部分题目 官方分类

    编程竞赛,特别是在线判题系统(如POJ,即Problem Online Judge)中的题目,是提升编程技能和算法理解的重要途径。POJ 1000 - 2000 是一个涵盖广泛的题目区间,包含了大量的初级到中级难度的问题,适合程序员们逐步...

    POJ1258-Agri-Net【Prim】

    解题的关键在于正确实现Prim算法,并确保其运行效率足够高,以满足POJ系统的时限要求。通常可以采用优先队列(如二叉堆)来优化查找最小边的过程,以降低时间复杂度。 **AC代码分析:** 解题报告中的"POJ1258-Agri-...

    魔兽世界终极版POJ的-测试数据

    这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q

    POJ1837-Balance

    1. "POJ1837-Balance.cpp":这是使用C++语言编写的源代码文件,其中包含了解决"POJ1837-Balance"问题的算法和程序。通过阅读代码,我们可以了解具体的编程实现细节,如数据结构的选择、算法流程、变量定义等。 2. ...

    POJ2299-Ultra-QuickSort

    【标题】"POJ2299-Ultra-QuickSort"是北京大学在线判题系统POJ上的一道编程题目,其主要涉及的算法是快速排序(Ultra-QuickSort)。快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用...

    POJ1010-STAMPS

    【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...

    POJ3414-Pots

    标题“POJ3414-Pots”是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目主要考察的是算法设计和实现能力,通常涉及计算机科学中的数据结构和算法知识。 解题报告是参赛者在...

    POJ1003-Hangover

    根据题目"POJ1003-Hangover"的特性,我们可以推测这可能是一个涉及数据结构、算法或者数学逻辑的问题。在实际的解题过程中,参赛者可能需要理解题目的具体要求,例如处理输入输出、解决特定的计算问题或者设计有效的...

    POJ1009-Edge Detection

    在POJ这样的在线编程平台上,这类问题通常要求高效且准确的算法,因为它们需要处理各种大小的输入并在有限的时间内给出结果。 【压缩包子文件的文件名称列表】:"POJ1009-Edge Detection.cpp"、"POJ1009-Edge ...

    POJ2503-Babelfish

    2. "POJ2503-Babelfish.doc":这可能是一个Microsoft Word文档,通常用于存储解题报告,包括问题解析、算法设计、代码解释、运行结果以及可能的优化建议等。 结合这些信息,我们可以推测"POJ2503-Babelfish"可能是...

    POJ2525-Text Formalization【TrieTree】

    《POJ2525-Text Formalization:深入解析TrieTree》 在计算机科学的世界里,算法和数据结构是解决问题的关键。今天我们要探讨的是一个名为"POJ2525-Text Formalization"的问题,它涉及到一种高效的数据结构——Trie...

    POJ1002-487-3279【Hash+Qsort】

    3. "POJ1002-487-3279.doc":这是一个文档文件,很可能包含了详细的解题报告,详细阐述了解题过程、算法分析、代码实现及测试情况。 在哈希表的使用中,需要注意冲突解决策略,如开放寻址法、链地址法等。快速排序...

    POJ1201-Intervals

    【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...

Global site tag (gtag.js) - Google Analytics