uva: 544 – Heavy Cargo ( Floyd Warshall MaxiMin )

544 – Heavy Cargo

Problem analysis:

  • Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.

Solution analysis:

Java solution:


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Hashtable;
import java.util.Map;
import java.util.Scanner;

class Main_544_HeavyCargo {

    /**
     * Author: Mohammad Moniruzzaman    
     */

    public static void main(String[] args) {
        final int INF = Integer.MIN_VALUE;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);

        Map<String, Integer> cities;
        String line, start, end;
        int numVertexes, numEdges, load, testCase=0,source, dest;
        int[][] graph;

        while(true)
        {
            testCase++;

            numVertexes = sc.nextInt();
            numEdges = sc.nextInt();

            if(numVertexes ==0 ) break;

            cities =  new Hashtable<string, integer="">(numVertexes);
            graph = new int[numVertexes+1][numVertexes+1];

            for(int i=0; i < numVertexes; i++)
                for( int j=i; j < numVertexes; j++)
                    graph[i][j] = graph[j][i] = INF;
            
            //skip empty line
            sc.nextLine();
            
            for(int i=0; i < numEdges ; i++)
            {
                line = sc.nextLine();

                start = line.split(" ")[0];
                end = line.split(" ")[1];
                load = Integer.parseInt(line.split(" ")[2]);
                
                if(! cities.containsKey(start)) cities.put(start, cities.size());
                
                if(! cities.containsKey(end)) cities.put(end, cities.size());
                
                graph[cities.get(start)][cities.get(end)] = load;    
                graph[cities.get(end)][cities.get(start)] = load;
            }

            line = sc.nextLine();

            source = cities.get( line.split(" ")[0]);
            dest = cities.get(line.split(" ")[1]);

            ///Floyd-Warshall - MaxiMin            
            for(int k=0; k < numVertexes; k++)
                for(int i=0; i < numVertexes; i++)
                    for(int j=0; j < numVertexes; j++)
                    {
                        if(graph[i][k] != INF && graph[k][j] != INF)
                        {
                            graph[i][j] = Math.max(graph[i][j], Math.min(graph[i][k], graph[k][j]));
                        }
                    }

            System.out.printf("Scenario #%d%n",testCase);
            System.out.printf("%d tons%n%n",graph[dest]);
        }

    }

}

 

Sample Input 

4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0

Sample Output 

Scenario #1
80 tons

Scenario #2
170 tons

 

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: