UVa : 10801 (Lift Hopping)


// http://online-judge.uva.es/p/v108/10801.html
// Runtime : 0.012
// Dijkstra algorithm - SSSP ( Single Source Shortest Path )

// @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>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

struct liftInfo {
	int time;
	bool floors [100 + 5];
} lift [5 + 3];

struct FloorInfo {
	int floor_num;
	int cost;
	int liftNum;
} p, temp;

void reset ()
{
	for ( int i = 0; i < 8; i++ )
		memset (lift [i].floors, false, sizeof (lift [i].floors));
}

bool operator < ( FloorInfo A, FloorInfo B )
{
	return A.cost > B.cost;
}

int main ()
{
	int n, k;

	while ( scanf ("%d %d", &n, &k) != EOF ) {
		reset ();

		for ( int i = 0; i < n; i++ ) scanf ("%d", &lift [i].time);
		getchar ();

		char input [1000];

		for ( int i = 0; i < n; i++ ) {
			gets (input);
			char *pch;
			pch = strtok (input, " ");

			while ( pch != NULL ) {
				lift [i].floors [atoi (pch)] = true;
				pch = strtok (NULL, " ");
			}
		}

		int d [6] [100 + 10];

		for ( int i = 0; i < 6; i++ ) {
            for ( int j = 0; j < 110; j++ )
                d [i] [j] = INT_MAX;
		}

		for ( int i = 0; i < 6; i++ ) d [i] [0] = 0;

		priority_queue <FloorInfo> pq;
		p.floor_num = 0;
		p.cost = 0;

		for ( int i = 0; i < n; i++ ) {
			if ( lift [i].floors [0] ) {
				p.liftNum = i;
				pq.push (p);
			}
		}

		while ( !pq.empty () ) {
			p = pq.top ();
			pq.pop ();

			if ( p.cost > d [p.liftNum] [p.floor_num] ) continue;

			for ( int i = 0; i < 100; i++ ) { // floors
			    int nc = p.cost + lift [p.liftNum].time * abs (p.floor_num - i);
				if ( lift [p.liftNum].floors [i] && d [p.liftNum] [i] > nc ) {
					temp.floor_num = i;
					temp.cost = d [p.liftNum] [i] = nc;
					temp.liftNum = p.liftNum;
					pq.push (temp);
				}
			}

			for ( int i = 0; i < n; i++ ) {
				if ( lift [i].floors [p.floor_num] ) {
					temp.floor_num = p.floor_num;
					temp.cost = p.cost + 60;
					temp.liftNum = i;
					if ( d [i] [p.floor_num] > temp.cost ) {
                        d [i] [p.floor_num] = temp.cost;
                        pq.push (temp);
					}

				}
			}
		}

		int mini = INT_MAX;

		for ( int i = 0; i < 6; i++ ) {
            if (d [i] [k] < mini ) mini = d [i] [k];
		}

		if ( mini == INT_MAX ) printf ("IMPOSSIBLE\n");
		else printf ("%d\n", mini);

	}

	return 0;
}

// @END_OF_SOURCE_CODE

One thought on “UVa : 10801 (Lift Hopping)

  1. Critical Input : 
    5 66
    10 11 19 55 2
    0 1 3 5 7 9 13 15 20 25 30 99
    4 15 19 20 25 30 80
    3 15 20
    35 45 66 80 99
    0 1 2 3 4 5 6
    
    Output :
    1734
    

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