用JAVA编写输入格式:第一行是两个以空格符分隔的整数n和m;接下来的第二行到第m+1行,每行包含4个以空格分开的元素x,y,w和d来描述一条道路,其中x和y是一条长度为w的道路相连的两个农场的编号,d是字符N.E.S.或W,表示从x到y的道路的方向。 输出格式:给出最远的一对农场之间距离的整数。
时间: 2023-12-14 17:38:10 浏览: 64
以下是用Java编写的解题思路:
1. 首先读入输入数据,包括农场数量n和道路数量m,以及每条道路的起点、终点、长度和方向。
2. 根据道路方向,构造邻接矩阵或邻接表表示图。如果方向为N或S,则在x和y之间添加一条双向边;如果方向为E或W,则在y和x之间添加一条双向边。
3. 使用Floyd算法或Dijkstra算法求出图的最短路径矩阵或最短路径树。
4. 遍历最短路径矩阵或最短路径树,找到最长的路径长度,即为最远的一对农场之间的距离。
以下是Java代码示例:
```java
import java.util.*;
public class Main {
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 + 1][n + 1]; // 邻接矩阵表示图
// 初始化邻接矩阵,将所有边的权值初始化为无穷大
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = Integer.MAX_VALUE;
}
}
// 根据道路方向构造邻接矩阵
for (int i = 1; i <= m; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
int w = scanner.nextInt();
char d = scanner.next().charAt(0);
if (d == 'N' || d == 'S') {
graph[x][y] = graph[y][x] = w;
} else {
graph[y][x] = graph[x][y] = w;
}
}
// 使用Floyd算法求最短路径矩阵
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][k] != Integer.MAX_VALUE
&& graph[k][j] != Integer.MAX_VALUE
&& graph[i][j] > graph[i][k] + graph[k][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
// 找到最长的路径长度
int maxDistance = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (graph[i][j] != Integer.MAX_VALUE && graph[i][j] > maxDistance) {
maxDistance = graph[i][j];
}
}
}
System.out.println(maxDistance);
}
}
```
阅读全文