uva534: Modified Shortest Path, Minmax distance

uva534.md

UVA 534

題目

分析

最短路徑變形，求 minmax distance。

三角不等式從：

    dp[a][b] = shortest distance between Vertex a, b

    if dp[i][k] + dp[k][i] < dp[i][j]:
        dp[i][j] = dp[i][k] + dp[k][j]

變更為：

    dp[a][b] = minmax distance between Vertex a, b

    minmax = max(dp[i][k], dp[k][j])
    if minmax < dp[i][j]:
        dp[i][j] = minmax

以下二種程式碼，分別為使用 Floyd-Warshall 及 Dijkstra's.

AC Code 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

double d(int x1, int y1, int x2, int y2) {
    int dx = x1 - x2;
    int dy = y1 - y2;
    return sqrt((double) (dx * dx + dy * dy));
}

int main() {
    ios::sync_with_stdio(false);

    int N;
    int scenario_cnt = 1;
    while (cin >> N) {
        if (N == 0) break;

        int x[N];
        int y[N];
        for (int i = 0; i < N; i++)
            cin >> x[i] >> y[i];

        double dp[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                dp[i][j] = d(x[i], y[i], x[j], y[j]);

        // floyd warshall
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    double minmax = max(dp[i][k], dp[k][j]);
                    if (minmax < dp[i][j])
                        dp[i][j] = minmax;
                }
            }
        }

        cout << "Scenario #" << scenario_cnt << "\n";
        cout << "Frog Distance = "
             << fixed << setprecision(3) << dp[0][1] << "\n\n";

        scenario_cnt++;
    }

    return 0;
}

AC Code 2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>
#include <queue>
#include <iomanip>

using namespace std;

struct Edge {
    int to;
    double cost;

    bool operator > (const Edge& e) const {
        return cost > e.cost;
    }
};

double d(int x1, int y1, int x2, int y2) {
    int dx = x1 - x2;
    int dy = y1 - y2;
    return sqrt((double) (dx * dx + dy * dy));
}

double dijkstra(const vector<vector<Edge>>& graph, int S, int T) {
    const int N = graph.size();
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    double d[N];
    fill(d, d + N, 1000000000.0);

    pq.push(Edge{S, 0.0});
    d[S] = 0.0;

    while (!pq.empty()) {
        Edge top = pq.top();
        pq.pop();
        int v = top.to;

        if (top.cost > d[v])
            continue;

        if (v == T)
            break;

        for (size_t i = 0; i < graph[v].size(); i++) {
            // Edge e = graph[v][i];
            // if (d[e.to] > d[v] + e.cost) {
            //     d[e.to] = d[v] + e.cost;
            //     pq.push(Edge{e.to, d[e.to]});
            // }
            Edge e = graph[v][i];
            double minmax = max(d[v], e.cost);
            if (minmax < d[e.to]) {
                d[e.to] = minmax;
                pq.push(Edge{e.to, d[e.to]});
            }
        }
    }

    if (d[T] == 1000000000.0)
        return -1.0;
    return d[T];
}

int main() {
    ios::sync_with_stdio(false);

    int N;
    int scenario_cnt = 1;
    while (cin >> N) {
        if (N == 0) break;

        int x[N];
        int y[N];
        for (int i = 0; i < N; i++)
            cin >> x[i] >> y[i];

        vector<vector<Edge>> graph(N);
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++)  {
                double distance = d(x[i], y[i], x[j], y[j]);
                graph[i].push_back(Edge{j, distance});
                graph[j].push_back(Edge{i, distance});
            }
        }

        double ans = dijkstra(graph, 0, 1);
        cout << "Scenario #" << scenario_cnt << "\n";
        cout << "Frog Distance = "
             << fixed << setprecision(3) << ans << "\n\n";

        scenario_cnt++;
    }

    return 0;
}