1.
import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 523 Minimum Transport Cost
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=464
*
* @author Rolf Schirm
* @version 1.0, 06/15/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.760
*/
public class Main {

public static void main(String... args) throws Exception {
final BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));

final int tcCount = Integer.parseInt(reader.readLine());
boolean first = true;

for(int tc = 0; tc < tcCount; tc++) {
String line = reader.readLine();

// Überspringe Leerzeilen
while(line != null && line.isEmpty()) {
line = reader.readLine();
}

final Dijkstra djikstra = new Dijkstra(readCosts(reader,
countNumbers(line), line));

// Anfragen einlesen
while((line = reader.readLine()) != null && !line.isEmpty()) {
final String[] split = line.split(" ");
final int startNode = Integer.parseInt(split[0]);
final int finishNode = Integer.parseInt(split[1]);

// Leerzeile zwischen Datensätzen ausgeben
if(first) {
first = false;
} else {
System.out.println();
}

djikstra.printSolution(startNode, finishNode);
}
}
}

private static int[][] readCosts(BufferedReader reader, int nodes, String
line) throws Exception {
int[][] result = new int[nodes + 1][nodes];

String[] buffer = new String[nodes];
buffer[0] = line;

for(int i = 1; i < nodes; i++) {
buffer[i] = reader.readLine();
}

String[] split = reader.readLine().split(" ");
for(int i = 0; i < nodes; i++) {
result[nodes][i] = Integer.parseInt(split[i]);
}

for(int row = 0; row < nodes; row++) {
split = buffer[row].split(" ");
for(int col = 0; col < nodes; col++) {
if(row == col) {
result[row][col] = Integer.parseInt(split[col]);
} else {
final int cost = Integer.parseInt(split[col]);
if(cost < 0) {
result[row][col] = cost;
} else {
result[row][col] = cost + result[nodes][col];
}
}
}
}
return result;
}

private static int countNumbers(String line) {
int result = 1;

for(int i = 0; i < line.length(); i++) {
if(line.charAt(i) == ' ') {
result++;
}
}

return result;
}
}

class Dijkstra {

private final int nodes;
private final int[][] costs;
private final int[][] edges;
private final int[] edgeCount;

public Dijkstra(int[][] matrix) {
nodes = matrix.length - 1;
costs = matrix;

edges = new int[nodes][nodes];
edgeCount = new int[nodes];

// Generieren der Kantenliste
for(int row = 0; row < nodes; row++) {
for(int col = 0; col < nodes; col++) {
if(costs[row][col] >= 0) {
edges[row][edgeCount[row]++] = col;
}
}
}
}

/**
* Gibt den Lösung für den kürzesten Weg zwischen einem
* Start- und eine Zielknoten über die Standardausgabe aus.
*/
public void printSolution(int startNode, int finishNode) {
if(startNode == finishNode) {
System.out.println("From " + startNode + " to " + finishNode + " :");
System.out.println("Path: " + startNode + "-->" + finishNode);
System.out.println("Total cost : 0");
} else {
final int startIndex = startNode - 1;
final int finishIndex = finishNode - 1;

final int[] solution = calcSolution(startIndex, finishIndex);

String pathString = "";

for(int index = finishIndex; index != startIndex; index =
solution[index]) {
pathString = "-->" + (index + 1) + pathString;
}

System.out.println("From " + startNode + " to " + finishNode + " :");
System.out.println("Path: " + startNode + pathString);
System.out.println("Total cost : " + (solution[startIndex] -
costs[nodes][finishIndex]));
}
}

/**
* Berechnet den kürzesten Weg zwischen einem Start- und einem
* Zielknoten mit dem Dijkstra-Algorithmus, der Rückgabewert ist
* ein Integer-Array mit den Vorgängerknoten ausser beim Index
* des Startknotens, dort derkürzeste Weg vom Start- zum Zielknoten.
*/
private int[] calcSolution(int startIndex, int finishIndex) {
// Zeigt an ob ein Knoten bereits fertig ist
final boolean[] isFinal = new boolean[nodes];

// Speicherung der minimalen Kosten zu jedem Knoten
final int[] minCosts = initializeMinCosts(startIndex, nodes);

// Speicherung der Vorgängerknoten zur Pfadrekonstruktion
final int[] order = new int[nodes];

// Hauptschleife
while(true) {
// Suche kleinsten freien Knoten
int current = getMinNode(isFinal, minCosts);
int currentCost = minCosts[current];

// Abbruchkriterium der Schleife
if(current < 0 || current == finishIndex) {
break;
}

// Markiere aktuellen Knoten als fertig
isFinal[current] = true;

// Mögliche Kanten
final int currentEdgeCount = edgeCount[current];
final int[] currentEdges = edges[current];

// Schleife über alle Knoten
for(int i = 0; i < currentEdgeCount; i++) {
final int next = currentEdges[i];

// Nur nichtfertige Knoten betrachten
if(!isFinal[next]) {
// Kante zwischen current und next
final int wayCost = costs[current][next];

// Kante muss existieren - entfällt wegen Kantenliste
// if(wayCost >= 0) {
// Neue Kosten vom Startknoten bis zum Knoten next
final int newCost = currentCost + wayCost;

// Alte Kosten vom Startknoten bis zum Knoten next
final int oldCost = minCosts[next];

// Prüfen ob neue minimale Kosten gefunden sind
if(oldCost < 0 || newCost < oldCost) {
// Neue minimale Kosten speichern
minCosts[next] = newCost;

// Neuen Vorgängerknoten speichern
order[next] = current;
}
//}
}
}
}

// Speichern der minimalen Kosten vom Startknoten
// bis zum Zielknoten im Index der Startknotens
order[startIndex] = minCosts[finishIndex];
return order;
}

/**
* Sucht den Knoten mit den minimalen Kosten der noch
* frei ist und gibt diesen als Rückgabewert zurück.
*/
private int getMinNode(boolean[] isFinal, int[] minCosts) {
int current = -1;
int currentCost = -1;
for(int i = 0; i < nodes; i++) {
// Knoten ist frei und ist vom Startknoten aus zu erreichen
if(!isFinal[i] && minCosts[i] >= 0) {
// Vergleiche minimale Kosten zu den Knoten
if(current < 0 || minCosts[i] < currentCost) {
current = i;
currentCost = minCosts[current];
}
}
}
return current;
}

/**
* Erzeugt ein Integer-Array mit und initialisiert es überall
* mit dem Wert -1, ausser bei dem index startIndex, dort mit
* dem Wert 0 und gibt dieses als Rückgabewert zurück.
*/
private int[] initializeMinCosts(int startIndex, int nodes) {
int[] array = new int[nodes];

for(int i = 0; i < nodes; i++) {
if(startIndex == i) {
array[i] = 0;
} else {
array[i] = -1;
}
}

return array;
}
}