uva 1001（最短路）

时间：2022-02-06 09:29:59

题意：在一个三维的奶酪里面有n（n<=100）个洞，老鼠A想到达老鼠B的位置，在洞里面可以瞬间移动，在洞外面的移动速度为10秒一个单位，求最短时间

题解：如果两个洞相交，那么d[i][j]=0；如果不相交，那么d[i][j]=dist-(r[i]+r[j]),dist为这两个洞圆心之间的欧几里得距离

再用Dijkstra处理就可以了

#include <cstdio>

#include <iostream>

#include <sstream>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <algorithm>

using namespace std;

#define ll long long

#define _cle(m, a) memset(m, a, sizeof(m))

#define repu(i, a, b) for(int i = a; i < b; i++)

#define repd(i, a, b) for(int i = b; i >= a; i--)

#define sfi(n) scanf("%d", &n)

#define sfd(n) scanf("%lf", &n)

#define pfi(n) printf("%d\n", n)

#define pfd(n) printf("%lf\n", n)

#define sfi2(n, m) scanf("%d%d", &n, &m)

#define sfd2(n, m) scanf("%lf%lf", &n, &m)

#define pfi2(n, m) printf("%d %d\n", n, m)

#define pfi3(a, b, c) printf("%d %d %d\n", a, b, c)

#define maxn 105

double dd[maxn][maxn];

struct Cir{

   double x, y, z, r;

}c[maxn];

double get_d(Cir c1, Cir c2)

{

    return sqrt((c1.x - c2.x) * (c1.x - c2.x) +

                (c1.y - c2.y) * (c1.y - c2.y) +

                (c1.z - c2.z) * (c1.z - c2.z));

}

const double inf = 1000000000000.0;

struct Dijkstra {

    int n;    //图,须手动传入！

    double E[maxn][maxn], d[maxn];

    int p[maxn];    //最短路径，父亲

    void init(int n) {

        this->n = n;

        repu(i, , n) repu(j, , n)

        E[i][j] = dd[i][j];

    }

    void solve(int s) {

        static bool vis[maxn];

        memset(vis, , sizeof(vis));

        memset(p, , sizeof(p));

        repu(i, , n + ) d[i] = inf;

        d[s] = 0.0;

        //repu(i, 0, n) pfd(d[i]);

        while() {

            int u = -;

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

                if(!vis[i] && (u == -||d[i] < d[u])) {

                    u = i;

                }

            }

            if(u == - || d[u] == inf) break;

            vis[u] = true;

            for(int v = ; v < n; v ++) {

                if(d[u] + E[u][v] < d[v]) {

                    d[v] = d[u] + E[u][v];

                    p[v] = u;

                }

            }

        }

    }

} dij;

int main()

{

    int n;

    int kase = ;

    while(~sfi(n) && n != -)

    {

        kase++;

        repu(i, , n + )

        sfd2(c[i].x, c[i].y), sfd2(c[i].z, c[i].r);

        sfd2(c[].x, c[].y), sfd(c[].z);

        sfd2(c[n + ].x, c[n + ].y), sfd(c[n + ].z);

        c[].r = c[n + ].r = 0.0;

        repu(i, , n + )

        repu(j, , n + )

        {

           dd[i][j] = get_d(c[i], c[j]) - (c[i].r + c[j].r);

           if(dd[i][j] < 0.0) dd[i][j] = 0.0;

           //printf("%d %d %lf\n", i, j, dd[i][j]);

        }

        dij.init(n + );

        dij.solve();

        //repu(i, 0, n + 2) pfd(dij.d[i]);

        printf("Cheese %d: Travel time = %d sec\n",

                     kase, (int)round(dij.d[n + ] * 10.0));

    }

    return ;

}

相关文章