1. 

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10099 The Tourist Guide
* 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 counter = 0;
int numOfCities;

while((numOfCities = scanner.nextInt()) != 0) // Input ends with 0
{
counter++;
int numOfRoads = scanner.nextInt();

/**
* Kapazitätsmatrix
* c[i,j] ist die Kapazität der Route von i nach j, falls eine solche Route existiert.
* Falls es keine Route von i nach j gibt ist c[i,j] 0.
*/
int[][] c = new int[numOfCities][numOfCities];

// read Roads
for(int i=0;i<numOfRoads;i++)
{
// lese Städte a,b und speichere index (x-1)
int a = scanner.nextInt()-1;
int b = scanner.nextInt()-1;

int abCapacity = scanner.nextInt();

// Bidirektional: Kapazität der Route in beiden Richtungen speichern
c[a][b] = abCapacity;
c[b][a] = abCapacity;
}

findMaxCapacities(c);

// read Route request
int a = scanner.nextInt()-1;
int b = scanner.nextInt()-1;
int tourists = scanner.nextInt();

// Calculate number of Trips
int capacity = c[a][b]-1; // einen Platz abziehen fĂ¼r den Tourist Guide
int trips = tourists / capacity;
if(tourists % capacity > 0) trips++;

// Output
out.println("Scenario #"+counter);
out.println("Minimum Number of Trips = "+trips);
out.println();
out.flush();
}
}

/**
* Algorithmus angelehnt an Floy-Warshall.
* c[i,j] ist die Kapazität der Route von i nach j, falls eine solche Route existiert. Falls es keine Route von i nach j gibt ist c[i,j] 0.
* Mit diesem Verfahren werden in der Matrix c die Routen mit den höchsten Kapazitäten bestimmt.
* @param c Kapazitätsmatrix
*/
private static void findMaxCapacities(int[][] c)
{
for(int k = 0; k < c.length; k++)
for(int i=0;i < c.length; i++)
for(int j=0;j < c.length; j++)
{
// c[i][j] ist Kapazität von i zu j
// Alternative Route: i -> k und k -> j

// Kapazität der alternativen route i -> k und k -> j
int altC = c[i][k] < c[k][j] ? c[i][k] : c[k][j];

// PrĂ¼fe ob alternative Route höhere Kapazität hat
if(altC > c[i][j]) c[i][j] = altC; // wenn ja wird alternative Kapazität gespeichert
}
}
}


2.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10099 The Tourist Guide
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1040
*
* @author Schirm , Mathauser , Mohr

* @version 1.0, 06/05/09
*
* Status : Accepted
* Runtime: 0.492
*/

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int testcase = 1;
int cities;
int roadsegments;
int start;
int end;
int passengers;

while (true) {
cities = sc.nextInt();
roadsegments = sc.nextInt();

int[][] ways = new int[cities][cities];

if (cities == 0 && roadsegments == 0)
break;

for (int i = 0; i < roadsegments; i++) {
int num1 = sc.nextInt() - 1;
int num2 = sc.nextInt() - 1;
int value = sc.nextInt() - 1;
ways[num1][num2] = value;
ways[num2][num1] = value;
}

/*
* for (int i = 0; i < ways.length; i++) { for (int j = 0; j <
* ways.length; j++) System.out.print(ways[i][j]+"\t");
* System.out.println(); }
*/

start = sc.nextInt() - 1;
end = sc.nextInt() - 1;

// Startort ist Zielort
if (start == end) {
System.out.println("Scenario #" + testcase);
System.out.println("Minimum Number of Trips = 0");
System.out.println();
}

else {
passengers = sc.nextInt();
ArrayList<Integer> toDoList = new ArrayList<Integer>();

// Alle Knoten die vom Startknoten wegführen in toDoList
// hinzufügen
for (int i = 0; i < ways.length; i++)
if (ways[start][i] != 0)
toDoList.add(i);

// Schleife laufen lassen bis das toDoList leer ist
while (!toDoList.isEmpty()) {

// Einen Knoten aus toDoList laden
int toDo = toDoList.get(0);

// Schleife über ways laufen lassen
for (int i = 0; i < ways.length; i++) {

// i darf nicht der Startknoten sein und es muss eine
// Verbindung zwischen dem Knoten toDo und i bestehen
if (i != start && ways[toDo][i] != 0) {

// Minimum der beiden Strecken start-toDo und toDo-i
int min = ways[start][toDo] < ways[toDo][i] ? ways[start][toDo]
: ways[toDo][i];

// min muss größer sein als die Strecke vom
// Startknoten zum Knoten i, dann der Strecke
// start-i den Wert min zuweisen
if (min > ways[start][i]) {
ways[start][i] = min;
ways[i][start] = min;

// Alle Knoten die mit i verbunden sind
// in die toDoList hinzufügen
for (int j = 0; j < ways.length; j++)
if (j != start && ways[i][j] != 0)
if (!toDoList.contains(j))
toDoList.add(j);
}
}
}

// Bearbeiteten Knoten löschen
toDoList.remove(0);
}

// Berechnung der Trips
int trips = passengers / ways[start][end];

// Trips um eins erhöhen wenn bei der Divison ein Rest
// entstanden ist
if (passengers % ways[start][end] != 0)
trips++;

// Ausgabe
System.out.println("Scenario #" + testcase);
System.out.println("Minimum Number of Trips = " + trips);
System.out.println();
}
testcase++;
}
}
}