Форум DL

Мой профиль

Это анализ задачи USACO 2007 November Silver: Problem 1. Cow Hurdles

USACO NOV07 Silver Problem 'hurdles' Analysis
by Neal Wu
First of all, it is clear that this problem can be converted into a (directed) graph, and for each of the T queries, we wish to find the shortest path between two nodes A and B.

One possible solution is for every query, use either a single-source shortest path algorithm (such as Dijkstra) or do a depth-first search to find the shortest path. However, this can take up to O(N^2) time for each query, and would then have a total running time of O(N^2 * T), which is too large for this problem's constraints. (N ≤ 300 and T ≤ 40,000).

Thus, we instead want to find a way to precompute all of the shortest paths beforehand. We do this by initializing all distances between two nodes A and B to the cost of the edge between A and B, or infinity if no such edge exists. Then we run the standard Floyd-Warshall algorithm, more info can be found in the Training pages or here:

http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm

to compute the shortest paths, with one difference: If cost (a, b, c,...) represents the cost of traveling from a to b and then from b to c, etc., then instead of

cost (i, j, k) = cost (i, j) + cost (j, k)

we now have
cost (i, j, k) = max (cost (i, j), cost (j, k)).

(The proof that this method does correctly find the shortest path is left to the reader.)
After computing the all-pairs shortest paths, we then input each query and output the result (in constant time for each query). Note that if the distance between A and B is still infinity after running the shortest path algorithm, it means that no path exists from A to B, so we output -1. Our total running time is thus O(N^3 + T), since the Floyd-Warshall takes O(N^3) time to compute the shortest paths, and each query takes O(1) time. Note that the Floyd-Warshall can be optimized to O(NM), where M is the number of edges.

The following is a solution using this idea:

#include <fstream>
using namespace std;

ofstream fout ("hurdles.out");
ifstream fin ("hurdles.in");

const int INF = 1000000000;
const int MAXN = 305;

int N, M, T;
int dist [MAXN][MAXN];

int main () {
    // initialize to infinity:
    memset (dist, 63, sizeof (dist));

    fin >> N >> M >> T;

    int a, b, c;

    // input data:
    for (int i = 0; i < M; i++) {
        fin >> a >> b >> c;
        a--, b--;   // use 0-based indexing
        dist [a][b] = min (dist [a][b], c);
    }

    // compute the shortest paths using Floyd-Warshall:
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            if (dist [i][k] < INF)
                for (int j = 0; j < N; j++)
                    if (max (dist [i][k], dist [k][j]) < dist [i][j])
                        dist [i][j] = max (dist [i][k], dist [k][j]);

    // output results:
    for (int i = 0; i < T; i++) {
        fin >> a >> b;
        a--, b--;
        fout << (dist [a][b] < INF ? dist [a][b] : -1) << '\n';
    }
    return 0;
}

Мой профиль

Это анализ задачи USACO 2007 November GOLD: Problem 1. Cow Relays

USACO NOV07 Gold Problem 'relays' Analysis
by Neal Wu
First, note that there cannot be more than T distinct nodes in our graph, because there are exactly T edges in the graph, and each node is an endpoint for at least two edges.

The simplest solution that is reasonably fast is to let s[L][V] be the shortest path from node S to node V that has length L. We can compute the values in this array by iterating N times, each time trying to travel through one edge from each node. The memory for this can be reduced by using a sliding window (since computing the values for length L only uses the values for length L - 1), and this solution uses O(N T2) time. To obtain a faster solution, we do the following.

Assume we have the shortest path, from S to E, of length N. Then we can break up this path into smaller paths whose lengths are powers of two. Thus, we can compute, for each power of two that is no greater than N, the shortest path between every pair of nodes that has a length of that power of two. This can be done using a method similar to Floyd-Warshall in O(T3 log N) time. (See the code below for more details.)

After we compute the shortest paths mentioned above, we can compute shortest paths, of length N, from S to every other node. We do this by breaking N up into its binary representation, and for each power of two that occurs, we compute shortest paths after adding in paths of length equal to this power. This can be done in O(T2 log N) time. (Again, see the code below for more details.) Thus, our overall runtime is O(T3 log N).

#include <cstdio>
#include <cstring>
using namespace std;

FILE *fout = fopen ("relays.out", "w");
FILE *fin = fopen ("relays.in", "r");

const int INF = 1000000000;
const int MAXV = 105;
const int MAXI = 1005;
const int MAXL = 20;

int N, V, T, S, E;

// compress nodes to smaller values
int change [MAXI];

// shortest path between two nodes with a length of a power of two
int dist [MAXL][MAXV][MAXV];

// best path from S to a node
int best [MAXV], best2 [MAXV];

// change a node to a 'compressed' value
inline void check (int &ind)
{
    if (change [ind] == -1)
        change [ind] = V++;

    ind = change [ind];
}
 
int main () {
// initialize arrays
    memset (change, -1, sizeof (change));
    memset (dist, 63, sizeof (dist));
    memset (best, 63, sizeof (best));

    fscanf (fin, "%d %d %d %d", &N, &T, &S, &E);

    check (S);
    check (E);

    for (int i = 0; i < T; i++) {
        int A, B, L;

        fscanf (fin, "%d %d %d", &L, &A, &B);

        check (A);
        check (B);

// edges are paths of length 1
        dist [0][A][B] <?= L;
        dist [0][B][A] <?= L;
    }

// compute shortest paths whose lengths are powers of two
// a path of length 2^p can be made by two paths of length 2^(p - 1)
    for (int p = 1; (1 << p) <= N; p++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist [p - 1][i][j] < INF)
                    for (int k = 0; k < V; k++)
                        if (dist [p - 1][i][j] + dist [p - 1][j][k] < dist [p][i][k])
                            dist [p][i][k] = dist [p - 1][i][j] + dist [p - 1][j][k];


// combine results of each power of two in the binary representation of N
    best [S] = 0;

    for (int p = 0; (1 << p) <= N; p++)
        if (N & (1 << p)) {
// use a temporary array 'best2' to hold the new values, and copy them to the old array afterward
            memset (best2, 63, sizeof (best2));

            for (int i = 0; i < V; i++)
                if (best [i] < INF)
                    for (int j = 0; j < V; j++)
                        if (best [i] + dist [p][i][j] < best2 [j])
                            best2 [j] = best [i] + dist [p][i][j];

            memcpy (best, best2, sizeof (best2));
        }

// best [E] is now the shortest path from S to E using N edges
    fprintf (fout, "%d\n", best [E]);

    return 0;
}

Мой профиль

На самом деле, тут обычный алгоритм Флойда (графы, 1).
Правда, в USACO 2007 November GOLD: Problem 1. Cow Relays используется слегка модифицированный:
положим,
F[s][i,j] - Кратчайший путь из i в j длиной 2^s,
тогда
F[s][i,j] = Max(F[s-1][i,k]+F[s-1][k,j], k=1..N) для s>1
и
F[1][i,j] = c[i,j] для всех дуг (i,j)
______________________
// LeX