UVa : 10099


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define N 1000000
#define INF INT_MIN
using namespace std;

int matrix [100 + 2] [100 + 2];

void reset (int n)
{
    for ( int i = 1; i <= n; i++ ) {
        for ( int j = 1; j <= n; j++ )
            matrix [i] [j] = INF;
        matrix [i] [i] = 0;
    }
}

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

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

        reset (n);

        for ( int i = 0; i < r; i++ ) {
            int c1;
            int c2;
            int p;

            scanf ("%d %d %d", &c1, &c2, &p);

            matrix [c1] [c2] = matrix [c2] [c1] = p - 1;
        }

        int source;
        int destination;
        int tourist;

        scanf ("%d %d %d", &source, &destination, &tourist);

        for ( int k = 1; k <= n; k++ ) {
            for ( int i = 1; i <= n; i++ ) {
                if ( matrix [i] [k] != INF ) {
                    for ( int j = 1; j <= n; j++ ) {
                        if ( matrix [k] [j] != INF && i != j )
                            matrix [i] [j] = max (matrix [i] [j], min (matrix [i] [k], matrix [k] [j]));
                    }
                }
            }
        }

        if ( source == destination ) {
            printf ("Scenario #%d\n", ++cases);
            printf ("Minimum Number of Trips = 1\n\n");
            continue;
        }

        int trip = tourist / matrix  [destination];

        if ( trip * matrix  [destination] < tourist )
            trip++;

        printf ("Scenario #%d\n", ++cases);
        printf ("Minimum Number of Trips = %d\n\n", trip);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

2 thoughts on “UVa : 10099

  1. Critical Input:
    5 6
    2 4 45
    1 2 35
    1 3 19
    2 5 96
    3 5 28
    2 3 17
    1 1 100
    5 6
    2 4 45
    1 2 35
    1 3 19
    2 5 96
    3 5 28
    2 3 17
    1 5 100
    5 7
    1 4 10
    2 4 45
    1 2 35
    1 3 19
    2 5 96
    3 5 28
    2 3 17
    1 5 100
    5 6
    2 4 45
    1 2 35
    1 3 19
    2 5 96
    3 5 28
    2 3 17
    5 2 25
    0 0
    
    Critical output :
    Scenario #1
    Minimum Number of Trips = 1
    
    Scenario #2
    Minimum Number of Trips = 3
    
    Scenario #3
    Minimum Number of Trips = 3
    
    Scenario #4
    Minimum Number of Trips = 1
    <<-- new line -- >>                                 
    

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