B - Frogger——spfa()

心已赠人 2022-06-12 05:11 155阅读 0赞

Think:  
1知识点：spfa()算法求最短路  
2题意：n = 1 的青蛙要跳到 n = 2 的青蛙哪里，可以其它石头作为中介，询问在可达路径中青蛙至少要能跳多远

[建议参考博客1][1]  
[建议参考博客2][2]

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <queue>
    #include <cmath>
    
    using namespace std;
    
    const int N = 240;
    const int inf = 0x3f3f3f3f;
    
    int n, x[N], y[N], vis[N];
    double e[N][N], dis[N];
    
    void spfa();
    
    int main(){
        int k = 1;
        while(scanf("%d", &n) && n){
            memset(e, 0, sizeof(e));
            for(int i = 1; i <= n; i++)
                scanf("%d %d", &x[i], &y[i]);
            for(int i = 1; i <= n; i++){
                for(int j = i; j <= n; j++){
                    double x_2 = (double)((x[i]-x[j])*(x[i]-x[j]));
                    double y_2 = (double)((y[i]-y[j])*(y[i]-y[j]));
                    e[i][j] = e[j][i] = sqrt(x_2 + y_2);
                }
            }
            spfa();
            printf("Scenario #%d\n", k++);
            printf("Frog Distance = %.3lf\n", dis[2]);
            printf("\n");
        }
        return 0;
    }
    void spfa(){
        queue <int> q;
        for(int i = 1; i <= n; i++)
            dis[i] = inf;
        ///memset(dis, inf, sizeof(dis));不能将double类型的数组初始化为无穷大
        memset(vis, 0, sizeof(vis));
        q.push(1);
        dis[1] = 0, vis[1] = 1;
        while(!q.empty()){
            int t1 = q.front();
            q.pop();
            vis[t1] = 0;
            for(int v = 1; v <= n; v++){
                if(max(dis[t1], e[t1][v]) < dis[v]){
                    dis[v] = max(dis[t1], e[t1][v]);
                    if(vis[v] == 0){
                        q.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
    }

[1]: http://blog.csdn.net/riba2534/article/details/54583589
[2]: http://www.cnblogs.com/liuxin13/p/4652009.html
[vjudge]: https://vjudge.net/contest/163006#problem/B