B - Frogger POJ - 2253————最短路变形

素颜马尾好姑娘i 2023-08-17 16:31 100阅读 0赞

[题目链接->][-]  
题意是：一个青蛙 到另一个青蛙的最短距离就是 最小必要跳跃的距离。  
其实这个题是单元最短路题变形体， 但是我为了简单 用了floyed， 这个时间也能过 ， 明天补题解

#include <cstdio>
    #include<iostream>
    #include<cmath>
    using namespace std;
    const double inf = 1e7;
    double mp[250][250];
    struct node { 
        double x, y;
    
    }marx[250];
    int n;
    void init()
    { 
        for(int i = 0;i <n;i++)
        { 
            for(int j = 0;j < n;j++)
            { 
                mp[i][j] = inf;
            }
        }
    
        for(int i = 0;i < n;i++)
        { 
            for(int j = 0;j < n;j++)
               		mp[j][i] = mp[i][j] = sqrt(pow(marx[i].x - marx[j].x, 2.0)+pow(marx[i].y - marx[j].y, 2.0));
        }
    
    }
    int main()
    { 
        int cnt = 0;
        while(cin >>n &&n!= 0)
        { 
            for(int i = 0;i <n;i++)
            { 
                cin>>marx[i].x>>marx[i].y;
            }
            init();
    
            for(int k = 0;k < n;k++)
            { 
                for(int i = 0;i < n;i++)
                { 
                    for(int j = 0;j < n;j++)
                    { 
                        if(mp[i][k]!= inf && mp[k][j]!=inf )
                        { 
    
                            mp[i][j] = min(mp[i][j], max(mp[i][k], mp[k][j]));
                        }
                    }
                }
            }
            printf("Scenario #%d\n", ++cnt);
            printf("Frog Distance = %.3f\n\n", mp[0][1]);
        }
        return 0;
    }

[-]: https://vjudge.net/contest/313997#problem/B