用java编写输入格式:第一行是两个以空格符分隔的整数n和m;接下来的第二行到第m+1行,每行包含4个以空格分开的元素x,y,w和d来描述一条道路,其中x和y是一条长度为w的道路相连的两个农场的编号,d是字符N.E.S.或W,表示从x到y的道路的方向。输出格式:给出最远的一对农场之间距离的整数。
时间: 2023-12-14 21:40:07 浏览: 63
以下是Java代码示例:
```java
import java.util.*;
public class FarmDistance {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 农场数量
int m = scanner.nextInt(); // 道路数量
int[][] graph = new int[n][n]; // 道路图,用邻接矩阵存储
for (int i = 0; i < m; i++) {
int x = scanner.nextInt() - 1; // 农场编号从1开始,转换为从0开始
int y = scanner.nextInt() - 1;
int w = scanner.nextInt();
char d = scanner.next().charAt(0);
if (d == 'N') {
graph[x][y] = w;
graph[y][x] = w;
} else if (d == 'E') {
graph[x][y] = w;
graph[y][x] = -w;
} else if (d == 'S') {
graph[x][y] = -w;
graph[y][x] = -w;
} else if (d == 'W') {
graph[x][y] = -w;
graph[y][x] = w;
}
}
scanner.close();
// Floyd算法求最短路径
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][k] != 0 && graph[k][j] != 0) {
int distance = graph[i][k] + graph[k][j];
if (graph[i][j] == 0 || distance > graph[i][j]) {
graph[i][j] = distance;
}
}
}
}
}
// 找到最远的一对农场之间的距离
int maxDistance = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
maxDistance = Math.max(maxDistance, graph[i][j]);
}
}
System.out.println(maxDistance);
}
}
```
这段代码首先读入农场数量n和道路数量m,然后用邻接矩阵存储道路图,其中每条道路的方向和长度都在读入时处理。接着使用Floyd算法求解每对农场之间的最短路径,最后找到最远的一对农场之间的距离输出即可。
阅读全文