(UVA) Meeting Prof. Miguel... - Solution 2
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=1112
If you want to see another solution for this problem, click here.
As the previous solution, this one also used Floyd-Warshall algorithm to solve this problem. The difference is that this solution has some improvements:
import java.io.*;
import java.util.*;
class Main {
public final int MAX_SIZE = 26;
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int numEdges = sc.nextInt();
while (numEdges != 0) {
// 3D matrix - 1st dimension is related to (young) and (mature)
int[][][] matrix = new int[2][MAX_SIZE][MAX_SIZE];
// iniate matrix (infinite)
for (int k = 0; k < 2; k++) {
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
matrix[k][i][j] = 10000000;
}
matrix[k][i][i] = 0; // from a place to itself, cost is zero
}
}
// read edges and fill matrix
for (int i = 0; i < numEdges; i++) {
char age = sc.next().charAt(0);
char direction = sc.next().charAt(0);
int n1 = sc.next().charAt(0)-'A';
int n2 = sc.next().charAt(0)-'A';
int cost = sc.nextInt();
int index = (age == 'Y')? 0 : 1;
matrix[index][n1][n2] = Math.min(matrix[index][n1][n2], cost);
if (direction == 'B') { // bidirectional
matrix[index][n2][n1] = Math.min(matrix[index][n2][n1], cost);
}
}
// check the minimum cost between every pair of node
for (int l = 0; l < 2; l++) {
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
for (int k = 0; k < MAX_SIZE; k++) {
matrix[l][j][k] = Math.min(matrix[l][j][k], matrix[l][j][i]+matrix[l][i][k]);
}
}
}
}
int minCost = 1000000000;
int start = sc.next().charAt(0)-'A';
int end = sc.next().charAt(0)-'A';
// check the minimum cost to meet, if it exists
for (int i = 0; i < MAX_SIZE; i++) {
if (matrix[0][start][i] == 10000000 || matrix[1][end][i] == 10000000) {
continue;
}
int totalCost = matrix[0][start][i]+matrix[1][end][i];
minCost = Math.min(minCost, totalCost);
}
// print answer
if (minCost == 1000000000) {
bw.write("You will never meet.\n"); // if it not exist a way to meet
}
else {
// check every place (node) to meet which has the minimum cost
bw.write(minCost+"");
for (int i = 0; i < MAX_SIZE; i++) {
int totalCost = matrix[0][start][i]+matrix[1][end][i];
if (totalCost == minCost) {
bw.write(" " + (char)(i+65));
}
}
bw.write("\n");
}
numEdges = sc.nextInt();
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
If you want to see another solution for this problem, click here.
As the previous solution, this one also used Floyd-Warshall algorithm to solve this problem. The difference is that this solution has some improvements:
- We only have one matrix with 3 dimensions. One of them is related to who is young and who is aged 30 or more.
- We do not use a map structure to map the letters to numbers. It is done simply by decreasing 'A' of the character read.
- We assume that the maximum number of letters (nodes) is 26 (A-Z).
import java.io.*;
import java.util.*;
class Main {
public final int MAX_SIZE = 26;
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int numEdges = sc.nextInt();
while (numEdges != 0) {
// 3D matrix - 1st dimension is related to (young) and (mature)
int[][][] matrix = new int[2][MAX_SIZE][MAX_SIZE];
// iniate matrix (infinite)
for (int k = 0; k < 2; k++) {
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
matrix[k][i][j] = 10000000;
}
matrix[k][i][i] = 0; // from a place to itself, cost is zero
}
}
// read edges and fill matrix
for (int i = 0; i < numEdges; i++) {
char age = sc.next().charAt(0);
char direction = sc.next().charAt(0);
int n1 = sc.next().charAt(0)-'A';
int n2 = sc.next().charAt(0)-'A';
int cost = sc.nextInt();
int index = (age == 'Y')? 0 : 1;
matrix[index][n1][n2] = Math.min(matrix[index][n1][n2], cost);
if (direction == 'B') { // bidirectional
matrix[index][n2][n1] = Math.min(matrix[index][n2][n1], cost);
}
}
// check the minimum cost between every pair of node
for (int l = 0; l < 2; l++) {
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
for (int k = 0; k < MAX_SIZE; k++) {
matrix[l][j][k] = Math.min(matrix[l][j][k], matrix[l][j][i]+matrix[l][i][k]);
}
}
}
}
int minCost = 1000000000;
int start = sc.next().charAt(0)-'A';
int end = sc.next().charAt(0)-'A';
// check the minimum cost to meet, if it exists
for (int i = 0; i < MAX_SIZE; i++) {
if (matrix[0][start][i] == 10000000 || matrix[1][end][i] == 10000000) {
continue;
}
int totalCost = matrix[0][start][i]+matrix[1][end][i];
minCost = Math.min(minCost, totalCost);
}
// print answer
if (minCost == 1000000000) {
bw.write("You will never meet.\n"); // if it not exist a way to meet
}
else {
// check every place (node) to meet which has the minimum cost
bw.write(minCost+"");
for (int i = 0; i < MAX_SIZE; i++) {
int totalCost = matrix[0][start][i]+matrix[1][end][i];
if (totalCost == minCost) {
bw.write(" " + (char)(i+65));
}
}
bw.write("\n");
}
numEdges = sc.nextInt();
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Comments
Post a Comment