UVa : 116 (Unidirectional TSP)


Title : Unidirectional TSP

Link : UVa 116

Tricky Lines :

If there is more than one path of minimal weight the path that is lexicographically smallest should be output.

Analysis :

  1. Calculate the sum from last column to first column
  2. u will get the lexicographically smallest path
  3. there is only 3 possible paths from a cell
  4. for example : if the dimension is row * column
  5. from cell [i] [j] u can go 3 possible path :
    • cell [(row + i – 1) % row] [j + 1];
    • cell [i] [j + 1];
    • cell [(row + i + 1) % row] [j + 1];
  6. suppose, u can go cell ‘c’, from cell ‘a’ and ‘b’
  7. and both path produces same path cost
  8. then update path for ‘c’, whichever is smallest, ‘a’ or ‘b’

Runtime : 0.116s

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>
#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 cell {
    int val;
    int child;
} matrix [10 + 3] [100 + 3];
int row, col;

void reset ()
{
    for ( int i = 0; i < row; i++ ) {
        for ( int j = 0; j < col; j++ )
            matrix [i] [j].child = -1;
    }
}

int main ()
{
    while ( scanf ("%d %d", &row, &col) != EOF ) {

        reset ();

        for ( int i = 0; i < row; i++ ) {
            for ( int j = 0; j < col; j++ ) scanf ("%d", &matrix [i] [j].val);
        }

        for ( int j = col - 2; j >= 0; j-- ) {
            for ( int i = 0; i < row; i++ ) {
                int thisNum = matrix [i] [j].val;

                matrix [i] [j].val = thisNum + matrix [(row + i - 1) % row] [j + 1].val;
                matrix [i] [j].child = (row + i - 1) % row;

                int sum = thisNum + matrix [i] [j + 1].val;
                if ( sum < matrix [i] [j].val ) {
                    matrix [i] [j].val = sum;
                    matrix [i] [j].child = i;
                }
                else if ( sum == matrix [i] [j].val && matrix [i] [j].child > i ) matrix [i] [j].child = i;

                sum = thisNum + matrix [(row + i + 1) % row] [j + 1].val;
                if ( sum < matrix [i] [j].val ) {
                    matrix [i] [j].val = sum;
                    matrix [i] [j].child = (row + i + 1) % row;
                }
                else if ( sum == matrix [i] [j].val && matrix [i] [j].child > (row + i + 1) % row ) matrix [i] [j].child = (row + i + 1) % row;
            }
        }

        int lowest = INT_MAX;
        int lowest_row;

        for ( int i = 0; i < row; i++ ) {
            if ( matrix [i] [0].val < lowest ) {
                lowest = matrix [i] [0].val;
                lowest_row = i;
            }
        }

        vector <int> path;

        for ( int i = 0; i < col; i++ ) {
            path.push_back (lowest_row + 1);
            lowest_row = matrix [lowest_row] [i].child;
        }

        bool space = false;
        for ( size_t i = 0; i < path.size (); i++ ) {
            if ( space ) printf (" ");
            space = true;
            cout << path [i];
        }
        cout << endl;
        cout << lowest << endl;
    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

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