UVa : 544 (Heavy Cargo)


Title : Heavy Cargo

Link : http://uva.onlinejudge.org/external/5/544.html

Tricky Lines :

  1. the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive.
  2. Roads can always be travelled in both directions.
  3. Blank line after each test case

Analysis :

  1. Floyd Warshall modified minimax algorithm
  2. roads can be traveled in both directions, so update cost for both d [i] [j] = d [j] [I]
  3. not every path’s cost is given, u need to calculate it. So initialize your cost array with negative number as u r going to find the max cost
  4. d [i] [j] = d [j] [i] = max (d [i] [j], min (d [i] [k], d [k] [j]));
  5. i’ve used map for city indexing
  6. cost of same city to same city is 0

Runtime : 0.048s

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;


int main ()
{
    int n, r;
    int cases = 0;

    while ( scanf ("%d %d", &n, &r) ) {
        if ( n == 0 && r == 0 ) break;

        map <string, int> cityIndex;
        string first, second;
        int cost;
        int index = 1;

        int d [205] [205];

        for ( int i = 0; i < 205; i++ ) {
            for ( int j = 0; j < 205; j++ ) d [i] [j] = -1;
            d [i] [i] = 0;
        }

        for ( int i = 0; i < r; i++ ) {
            cin >> first >> second >> cost;
            if ( !cityIndex [first] ) cityIndex [first] = index++;
            if ( !cityIndex [second] ) cityIndex [second] = index++;

            d [cityIndex [first]] [cityIndex [second]] = cost;
            d [cityIndex [second]] [cityIndex [first]] = cost;
        }

        for ( int k = 1; k <= n; k++ ) {
            for ( int i = 1; i <= n; i++ ) {
                for ( int j = 1; j <= n; j++ )
                    d [i] [j] = d [j] [i] = max (d [i] [j], min (d [i] [k], d [k] [j]));
            }
        }


        string source, dest;
        cin >> source >> dest;
        printf ("Scenario #%d\n", ++cases);
        printf ("%d tons\n\n", d [cityIndex ] [cityIndex [dest]]);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s