问题链接可以在这里找到。
问题陈述
Burger Town是一个由N个特殊交叉口和N-1条路径组成的城市。每对交叉口之间恰好有一条最短路径。第i个交叉口位于(xi,yi)，两个交叉口i和j之间的距离定义为出租车几何距离。
Tim最近买了一辆出租车来做出租车司机。他的车非常便宜，但有一个很大的缺点。在需要加油之前，它只能水平行驶H个单位，垂直行驶V个单位。
如果一个顾客想从交叉口i被带到另一个交叉口j，那么只有当这辆车的水平距离之和和竖直距离之和小于或等于H和V时，才能行驶这条路线。
此外，任意两个交叉口之间都有唯一的路径。
现在他正在考虑将车退还给卖家。但他首先想知道是否值得这样做。这就是为什么他想知道无序对(i,j)的数量，使得无法从交叉口i驾驶顾客到交叉口j。
限制条件
2 ≤ N ≤ 10^5
0 ≤ H,V ≤ 10^14
0 ≤ xi,yi ≤ 10^9
我用递归解决了这个问题。但在一些测试用例中，我的代码超时了。
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
long H = in.nextLong();
long V = in.nextLong();
List<Vertex> vertex = new ArrayList<>();
for (int i=0; i < N; i++) {
Vertex vx = new Vertex(in.nextLong(), in.nextLong());
vertex.add(vx);
}
for (int i=0; i < N-1; i++) {
int fromPath = in.nextInt()-1;
int toPath = in.nextInt()-1;
vertex.get(fromPath).neighbours.add(vertex.get(toPath));
vertex.get(toPath).neighbours.add(vertex.get(fromPath));
}
long count = 0;
for (int i=0; i < N; i++) {
count += (N - findUnorderedPairs(vertex.get(i), null, 0, 0, H, V));
}
System.out.println(count/2);
int temp = 0;
}
private static long findUnorderedPairs(Vertex vertex, Vertex previousVertex, long hor, long vert, long H, long V) {
if (hor > H || vert > V) {
return 0;
}
long result = 1;
for (Vertex v : vertex.neighbours) {
result += (v != previousVertex) ? findUnorderedPairs(v, vertex, hor + Math.abs(vertex.x - v.x), vert + Math.abs(vertex.y - v.y), H, V) : 0;
}
return result;
}
private static class Vertex {
private long x;
private long y;
public ArrayList<Vertex> neighbours;
public Vertex(long x, long y) {
this.x = x;
this.y = y;
neighbours = new ArrayList<>();
}
}
}
我也尝试了Dijkstra的实现，但也没有成功。
如果有任何建议帮助加快解决方案，将不胜感激。
任意两个连接点之间都有唯一的路径意味着这是一棵连通树，并且这条唯一路径也是最短路径。 - Pham Trung