Wednesday, December 31, 2014

UVa Problem 821 - Page Hopping

Problem:

Please find the problem here.

Solution:

Obviously, we should run all pairs shortest paths! Can't believe this is a real contest problem!

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=762

#include "UVa821.h"

#include <iostream>
#include <vector>
#include <map>
#include <iomanip>

using namespace std;

int UVa186_assign_node_number(map<int, int>& node_numbers, map<int, int>& node_namings, int node_name);

int UVa821()
{
    int test_case = 0;
    while (true)
    {
        test_case++;
        // Step 1: Read input
        vector<pair<int, int>> edges;
        map<int, int> node_namings;
        map<int, int> node_numbers;
        while (true)
        {
            int src_name;
            int dst_name;
            cin >> src_name;
            cin >> dst_name;
            if (src_name == 0 && dst_name == 0)
            {
                break;
            }

            int src_number = UVa186_assign_node_number(node_numbers, node_namings, src_name);
            int dst_number = UVa186_assign_node_number(node_numbers, node_namings, dst_name);

            edges.push_back(pair<int, int>(src_number, dst_number));
        }
        if (edges.size() == 0)
        {
            break;
        }

        // Step 2: Produce the data structures for Floyd Warshall
        int number_of_nodes = node_numbers.size();

        vector<vector<int> > adjacency_matrix;
        vector<vector<int> > distances;
        vector<vector<bool> > reachable;
        vector<vector<int> > path;
        adjacency_matrix.resize(number_of_nodes);
        distances.resize(number_of_nodes);
        reachable.resize(number_of_nodes);
        path.resize(number_of_nodes);
        for (int src = 0; src < number_of_nodes; src++)
        {
            adjacency_matrix[src].resize(number_of_nodes);
            distances[src].resize(number_of_nodes);
            reachable[src].resize(number_of_nodes);
            path[src].resize(number_of_nodes);

            for (int dst = 0; dst < number_of_nodes; dst++)
            {
                adjacency_matrix[src][dst] = 0;
                distances[src][dst] = -1;
                reachable[src][dst] = false;
                path[src][dst] = -1;
            }
        }

        for (unsigned int e = 0; e < edges.size(); e++)
        {
            pair<int, int> edge = edges[e];
            int src = edge.first;
            int dst = edge.second;

            // Beware of the input could have multiple edges!
            adjacency_matrix[src][dst] = 1;
            distances[src][dst] = 1;
            reachable[src][dst] = true;
            path[src][dst] = dst;
        }

        for (int k = 0; k < number_of_nodes; k++)
        {
            for (int src = 0; src < number_of_nodes; src++)
            {
                for (int dst = 0; dst < number_of_nodes; dst++)
                {
                    if (reachable[src][k] && reachable[k][dst]) // relaxation is possible if the proposal is valid
                    {
                        int current_distance = distances[src][dst];
                        int propose_distance = distances[src][k] + distances[k][dst];
                        if (!reachable[src][dst] || propose_distance < current_distance)
                        {
                            distances[src][dst] = propose_distance;
                            reachable[src][dst] = true;
                            path[src][dst] = path[src][k];
                        }
                    }
                }
            }
        }

        int sum = 0;
        int count = 0;
        for (int src = 0; src < number_of_nodes; src++)
        {
            for (int dst = 0; dst < number_of_nodes; dst++)
            {
                if (src != dst)
                {
                    sum += distances[src][dst];
                    count++;
                }
            }
        }
        cout << "Case " << test_case << ": average length between pages = " << setprecision(3) << fixed << ((double)sum) / count << " clicks" << endl;
    }

    return 0;
}

int UVa186_assign_node_number(map<int, int>& node_numbers, map<int, int>& node_namings, int node_name)
{
    int node_number;
    map<int, int>::iterator probe = node_numbers.find(node_name);
    if (probe == node_numbers.end())
    {
        node_number = node_numbers.size();
        node_numbers.insert(pair<int, int>(node_name, node_number));
        node_namings.insert(pair<int, int>(node_number, node_name));
    }
    else
    {
        node_number = probe->second;
    }

    return node_number;
}

No comments :

Post a Comment