HDU.1596 find the safest road (Floyd)

题意分析

与普通的最短路不太相同，本题有些许的变化。

1. 要找到由i到j最安全的路，故在求解的时候要保证mp[i][j]尽量大，而不是尽量小。

2. 当mp[i][j] = 0的时候表示无法通过，而不是为无穷大的时候无法通过。

3. 路程求解过程中，安全系数是相乘的关系，不是按照普通路径的相加的关系。

4. 此题n^3的Floyd竟然能过，我惊了。

代码总览

#include <bits/stdc++.h>

#define nmax 1005

using namespace std;

const double eps = 1e-5;

double mp[nmax][nmax];

int n,m;

void floyd()

{

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

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

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

                if(fabs(mp[i][k] - 0.0 ) <= eps || fabs(mp[k][j] - 0.0 ) <= eps )

                    continue;

                else{

                    double temp = mp[i][k] * mp[k][j];

                    if(temp > mp[i][j]){

                        mp[i][j] = temp;

                    }

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d",&n) !=EOF){

        memset(mp,0,sizeof(mp));

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

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

                scanf("%lf",&mp[i][j]);

            }

        }

        floyd();

        scanf("%d",&m);

        int sta, end;

        for(int i = 0; i<m;++i){

            scanf("%d %d",&sta,&end);

            double temp = mp[sta][end];

            if(fabs(temp - 0.0) <=eps)

                printf("What a pity!\n");

            else

                printf("%.3f\n",temp);

        }

    }

    return 0;

}