Dijkstra算法 最短路

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 210;
const double INF = 1e9;

PII point[N];
double g[N][N];
double dist[N];
bool st[N];
int n;

double get(int x1, int x2, int y1, int y2)
{
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

double dijkstra()
{
    memset(st, 0, sizeof st);
    for (int i = 1; i <= n; i ++)
            dist[i] = INF;
    dist[1] = 0;

    for (int i = 0; i < n; i ++)
    {
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; j ++)
        {
            dist[j] = min(dist[j], max(dist[t], g[t][j]));
        }
    }

    return dist[2];
}

int main()
{
    int cnt = 1;
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j++)
                g[i][j] = INF;

        memset(point, 0, sizeof point);
        for (int i = 1; i <= n; i ++)
            cin >> point[i].x >> point[i].y;

        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                if (i == j) g[i][j] = 0;
                else g[i][j] = g[j][i] = get(point[i].x, point[j].x, point[i].y, point[j].y);

        printf("Scenario #%d\n", cnt ++);
        printf("Frog Distance = %.3lf\n", dijkstra());
        puts("");
    }

    return 0;
}

Kruskal算法 最小生成树

/*
对于求最大最小或最小最大，可以用最小生成树

Kruskal算法：
当0和1都在同一个连通块中时，处于连通块的点都是可以到达的，
又由于边是从小到大排序的，所以第一次让0和1连通的边就是最小的一条边(相对于非树边而言)
*/
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 210, M = N * N;

int n, m;
struct Edge
{
    int a, b;
    double w;
    bool operator< (const Edge& W) const
    {
        return w < W.w;
    }
}e[M];
int p[N];
PII point[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

double dist(int i, int j)
{
    PII a = point[i], b = point[j];
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

void build()
{
    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j < n; j ++)
            e[m ++] = {i, j, dist(i, j)};
}

int main()
{
    int t = 1;
    while (cin >> n, n)
    {
        m = 0;

        for (int i = 0; i < n; i ++) p[i] = i;
        for (int i = 0; i < n; i ++)
        {
            int a, b;
            scanf("%d%d", &a, &b);

            point[i] = {a, b};
        }

        build();

        sort(e, e + m);

        for (int i = 0; i < m; i ++)
        {
            int a = find(e[i].a), b = find(e[i].b);
            double w = e[i].w;

            if (a != b)
            {
                p[a] = b;
                if (find(0) == find(1))
                {
                    printf("Scenario #%d\nFrog Distance = %.3lf\n\n", t ++, w);
                    break;
                }
            }
        }
    }

    return 0;
}