1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #383 Shipping Routes
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1103
*
* @author Fabian Seidl
* @author Marcel Sachse
* @version 1.0, 24/06/2009
*
* Status : Accepted
* Runtime: 0.088
*/

import java.io.*;
import java.util.*;

public class Main
{
private static PrintWriter out = new PrintWriter(System.out);
private static Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException
{
int numberOfDatasets = scanner.nextInt();

out.println("SHIPPING ROUTES OUTPUT");

for(int i = 1;i<=numberOfDatasets;i++)
{
out.println();
out.println("DATA SET "+i);
out.println();

readDataset();
}

out.println();
out.println("END OF OUTPUT");

out.flush();
}

/**
* Liest einen Datensatz ein, verarbeitet ihn und gibt die Ergebnisse aus.
* @throws IOException Abbruch bei IO Fehlren
*/
private static void readDataset() throws IOException
{
final int numOfWareHouses = scanner.nextInt(); // in Angabe M
final int numOfLegs = scanner.nextInt(); // in Angabe N
final int numOfRoutes = scanner.nextInt(); // in Angabe P
scanner.nextLine();

// Warenh├¤user lesen und als Liste speichern
String[] in = scanner.nextLine().split(" ");
List<String> wareHouses = Arrays.asList(in);

/**
* Gewichtsmatrix
* Wert von wMatrix[j,i] entspricht Anzahl ben├Âtigter Kanten um von j nach i zu kommen.
* Dabei steht j und i fìr den Index eines Warehouse in der Liste
* 0 bedeutet keine Verbindung.
*/
int[][] wMatrix = new int[wareHouses.size()][wareHouses.size()];

// Legs lesen

for(int i = 0; i<numOfLegs;i++)
{
String[] legIn = scanner.nextLine().split(" ");
int first = wareHouses.indexOf(legIn[0]);
int second = wareHouses.indexOf(legIn[1]);

// Leg in Gewichtsmatrix speichern
wMatrix[first][second] = 1;
wMatrix[second][first] = 1;
}

// Floyd Alghorithmus
floyd(wMatrix);

// Read Shipping Requests

for(int i=0;i<numOfRoutes;i++)
{
int shipSize = scanner.nextInt();
String[] route = scanner.nextLine().split("\\s+");

// Index von Start und Ziel holen
int start = wareHouses.indexOf(route[1]);
int end = wareHouses.indexOf(route[2]);

// Kosten berechnen
int costs = shipSize * wMatrix[start][end] * 100;

// Ausgabe
if(costs > 0) out.write("$"+costs+"\n");
else out.write("NO SHIPMENT POSSIBLE\n");
}


}

/**
* Floyd Algorithmus.
* w[i,j] ist das Gewicht der Kante von i nach j, falls eine solche Kante existiert. Falls es keine Kante von i nach j gibt ist w[i,j] 0.
* Mit diesem Verfahren werden in die Matrix w die kìrzesten Distanzen bestimmt.
* @param w Gewichtsmatrix
*/
private static void floyd(int[][] w)
{
for(int k = 0; k < w.length; k++)
{
for(int i=0;i < w.length; i++)
for(int j=0;j < w.length; j++)
{
int old = w[i][j];
int next = w[i][k] + w[k][j];

// spezlielle Abfrage da 0 = keine Verb.:
if(w[i][k] > 0 && w[k][j] > 0)
if(next < old || old == 0) w[i][j] = next;
}
}
}
}