1. 

package problemSetVolumes.volume005;

import java.util.*;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 544 - Heavy Cargo
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=485
*
* @author Siegfried Ippisch
* @version 1.0
*
* Method : Floyd–Warshall algorithm
* Status : Accepted
* Runtime: 0.736
*/
public class HeavyCargo {

public static void floydWarshall(int[][] adja){
int lenght = adja.length;
for (int k = 0; k < lenght; k++)
for (int i = 0; i < lenght; i++)
for (int j = 0; j < lenght; j++)
adja[i][j] = Math.max(adja[i][j], Math.min(adja[i][k], adja[k][j]));
}

public static void main(String[] args){
Scanner in = new Scanner(System.in);

int cities = in.nextInt();
int roads = in.nextInt();
int scenario = 1;
while(cities != 0 && roads != 0){

Map<String, Integer> names = new HashMap<String, Integer>();
int[][] adja = new int[cities][cities];
int index = 0;

for(int i=0; i<roads; i++){
String c1 = in.next();
String c2 = in.next();
int cost = in.nextInt();
int n1, n2;

if(names.containsKey(c1)){
n1 = names.get(c1);
} else{
n1 = index;
names.put(c1, index++);
}

if(names.containsKey(c2)){
n2 = names.get(c2);
} else{
n2 = index;
names.put(c2, index++);
}

adja[n1][n2] = cost;
adja[n2][n1] = cost;
}

floydWarshall(adja);

System.out.println("Scenario #" + scenario++);
System.out.println(adja[names.get(in.next())][names.get(in.next())] + " tons");
System.out.println();

cities = in.nextInt();
roads = in.nextInt();
}
}

}