用java输入格式:第一行是两个以空格符分隔的整数n和m;接下来的第二行到第m+1行,每行包含4个以空格分开的元素x,y,w和d来描述一条道路,其中x和y是一条长度为w的道路相连的两个农场的编号,d是字符N.E.S.或W,表示从x到y的道路的方向。输出格式:给出最远的一对农场之间距离的整数。
时间: 2024-01-21 18:16:07 浏览: 97
以下是Java的代码实现:
```java
import java.util.*;
public class Main {
static int n, m;
static int[][] dist;
static boolean[][][] vis;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static char[] dir = {'N', 'E', 'S', 'W'};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
dist = new int[n][n];
vis = new boolean[n][n][4];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], -1);
}
for (int i = 0; i < m; i++) {
int x = sc.nextInt() - 1;
int y = sc.nextInt() - 1;
int w = sc.nextInt();
char d = sc.next().charAt(0);
int dirIndex = Arrays.binarySearch(dir, d);
vis[x][y][dirIndex] = true;
vis[y][x][(dirIndex + 2) % 4] = true;
dist[x][y] = dist[y][x] = w;
}
floyd();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (dist[i][j] != -1) {
for (int k = 0; k < 4; k++) {
if (vis[i][j][k]) {
int x = i + dx[k] * dist[i][j];
int y = j + dy[k] * dist[i][j];
if (x >= 0 && x < n && y >= 0 && y < n && vis[j][x][(k + 2) % 4]) {
ans = Math.max(ans, dist[i][j] * 2);
}
}
}
}
}
}
System.out.println(ans);
}
static void floyd() {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != -1 && dist[k][j] != -1) {
if (dist[i][j] == -1 || dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
for (int d = 0; d < 4; d++) {
vis[i][j][d] = vis[i][k][d] || vis[k][j][d] || vis[i][j][d];
}
}
}
}
}
}
}
}
```
算法思路:
首先使用 Floyd 算法求出任意两个农场之间的最短距离和路径,同时记录下每条路径的方向。然后对于任意一对农场 $i,j$,枚举从 $i$ 到 $j$ 的路径上的方向 $d$,假设这条路径的长度为 $w$,则我们可以通过这条路径从 $i$ 和 $j$ 向前走 $w$ 步得到两个新的农场 $x,y$,如果 $x$ 和 $y$ 之间也有一条方向为 $d$ 的路径,则说明我们可以从 $i$ 通过这条路径到达 $j$,再通过这条路径回到 $i$,这样我们就找到了一对最远的农场,更新答案即可。
阅读全文