304 lines
7.1 KiB
Java
304 lines
7.1 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.Arrays;
|
|
import java.util.Comparator;
|
|
import java.util.HashMap;
|
|
import java.util.HashSet;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
import java.util.PriorityQueue;
|
|
import java.util.Set;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.Pair;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class TaskF extends SimpleSavingChelperSolution {
|
|
|
|
public static final long INF = Long.MAX_VALUE / 100;
|
|
private Map<Integer, Map<Integer, Long>> edges;
|
|
private int n;
|
|
private int m;
|
|
private int treeCount;
|
|
private int[] vertexTreeId;
|
|
private Set<Integer> treeEgressPointsSet;
|
|
private int[] vertexTreeHeight;
|
|
private long[] vertexTreeLength;
|
|
private boolean[] tainted;
|
|
private int[] dfsIn;
|
|
private int[] dfsOut;
|
|
private int timer;
|
|
private int[][] upside;
|
|
private List<List<Integer>> egressPointsByTree;
|
|
private List<int[]> edges2Dest;
|
|
private List<long[]> edges2Dist;
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
TaskF task = this;
|
|
|
|
Thread thread = new Thread(null, new Runnable() {
|
|
@Override
|
|
public void run() {
|
|
task.wrapSolve(testNumber, in, out);
|
|
}
|
|
}, "Test", 1 << 26);
|
|
thread.start();
|
|
try {
|
|
thread.join();
|
|
} catch (InterruptedException e) {
|
|
throw new RuntimeException(e);
|
|
}
|
|
|
|
// wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
static final int UPSIDE_L = 20;
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
long startTime = System.nanoTime();
|
|
|
|
n = in.nextInt();
|
|
m = in.nextInt();
|
|
|
|
edges = new HashMap<>();
|
|
for (int i = 0; i < n; i++) {
|
|
edges.put(i, new HashMap<>());
|
|
}
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
int a = in.nextInt() - 1;
|
|
int b = in.nextInt() - 1;
|
|
long c = in.nextLong();
|
|
|
|
edges.get(a).put(b, c);
|
|
edges.get(b).put(a, c);
|
|
}
|
|
|
|
treeCount = 0;
|
|
vertexTreeId = new int[n];
|
|
vertexTreeHeight = new int[n];
|
|
vertexTreeLength = new long[n];
|
|
Arrays.fill(vertexTreeId, -1);
|
|
|
|
treeEgressPointsSet = new HashSet<>();
|
|
|
|
dfsIn = new int[n];
|
|
dfsOut = new int[n];
|
|
timer = 1;
|
|
|
|
upside = new int[n][UPSIDE_L + 1];
|
|
for (int i = 0; i < n; i++) {
|
|
Arrays.fill(upside[i], -1);
|
|
}
|
|
|
|
tainted = new boolean[n];
|
|
|
|
treefy();
|
|
// treefy2();
|
|
|
|
debug.println("Treefy finish " + (System.nanoTime() - startTime) / 1e9);
|
|
debug.println("Trees: " + treeCount);
|
|
debug.println("TEP: " + treeEgressPointsSet.size());
|
|
|
|
egressPointsByTree = new ArrayList<>();
|
|
for (int i = 0; i < treeCount; i++) {
|
|
egressPointsByTree.add(new ArrayList<>());
|
|
}
|
|
|
|
for (int v1 : treeEgressPointsSet) {
|
|
egressPointsByTree.get(vertexTreeId[v1]).add(v1);
|
|
}
|
|
|
|
edges2Dest = new ArrayList<>();
|
|
edges2Dist = new ArrayList<>();
|
|
|
|
for (int v = 0; v < n; v++) {
|
|
int m = edges.get(v).size();
|
|
|
|
int[] dest = new int[m];
|
|
long[] dist = new long[m];
|
|
int k = 0;
|
|
for (Map.Entry<Integer, Long> entry : edges.get(v).entrySet()) {
|
|
int vv = entry.getKey();
|
|
long c = entry.getValue();
|
|
|
|
dest[k] = vv;
|
|
dist[k] = c;
|
|
k++;
|
|
}
|
|
edges2Dest.add(dest);
|
|
edges2Dist.add(dist);
|
|
}
|
|
|
|
Map<Integer, long[]> egressDistances = new HashMap<>();
|
|
for (int origin : treeEgressPointsSet) {
|
|
long[] distances = new long[n];
|
|
Arrays.fill(distances, INF);
|
|
distances[origin] = 0;
|
|
|
|
egressDistances.put(origin, distances);
|
|
|
|
egressDijkstra(origin, distances);
|
|
}
|
|
debug.println("Dijkstra finish " + (System.nanoTime() - startTime) / 1e9);
|
|
|
|
debug.println("preprocess finish " + (System.nanoTime() - startTime) / 1e9);
|
|
|
|
int requestCount = in.nextInt();
|
|
for (int i = 0; i < requestCount; i++) {
|
|
int a = in.nextInt() - 1;
|
|
int b = in.nextInt() - 1;
|
|
|
|
long res = INF;
|
|
|
|
if (vertexTreeId[a] == vertexTreeId[b]) {
|
|
res = Math.min(res, insideTreeDistance(a, b));
|
|
}
|
|
|
|
for (int v1 : egressPointsByTree.get(vertexTreeId[a])) {
|
|
long dist = egressDistances.get(v1)[a] + egressDistances.get(v1)[b];
|
|
|
|
res = Math.min(res, dist);
|
|
}
|
|
|
|
out.println(res);
|
|
}
|
|
}
|
|
|
|
boolean isUpsideInTree(int a, int b) {
|
|
return dfsIn[a] <= dfsIn[b] && dfsOut[a] >= dfsOut[b];
|
|
}
|
|
|
|
int lca(int a, int b) {
|
|
if (isUpsideInTree(a, b)) {
|
|
return a;
|
|
}
|
|
if (isUpsideInTree(b, a)) {
|
|
return b;
|
|
}
|
|
for (int l = UPSIDE_L; l >= 0; l--) {
|
|
if (upside[a][l] == -1) {
|
|
continue;
|
|
}
|
|
if (!isUpsideInTree(upside[a][l], b)) {
|
|
a = upside[a][l];
|
|
}
|
|
}
|
|
return upside[a][0];
|
|
}
|
|
|
|
long insideTreeDistance(int v1, int v2) {
|
|
int l = lca(v1, v2);
|
|
|
|
return vertexTreeLength[v1] + vertexTreeLength[v2] - vertexTreeLength[l] * 2;
|
|
}
|
|
|
|
void treefyDfs(int v, List<Integer> stack) {
|
|
dfsIn[v] = timer++;
|
|
|
|
for (Map.Entry<Integer, Long> edge : edges.get(v).entrySet()) {
|
|
int vv = edge.getKey();
|
|
long c = edge.getValue();
|
|
|
|
if (vertexTreeId[vv] == -1 && !tainted[vv]) {
|
|
for (Map.Entry<Integer, Long> edge2 : edges.get(vv).entrySet()) {
|
|
int vvv = edge2.getKey();
|
|
|
|
if (vertexTreeId[vvv] == vertexTreeId[v] && vvv != v) {
|
|
tainted[vv] = true;
|
|
}
|
|
}
|
|
|
|
if (tainted[vv]) {
|
|
continue;
|
|
}
|
|
|
|
vertexTreeId[vv] = vertexTreeId[v];
|
|
vertexTreeHeight[vv] = vertexTreeHeight[v] + 1;
|
|
vertexTreeLength[vv] = vertexTreeLength[v] + c;
|
|
|
|
stack.add(vv);
|
|
|
|
for (int l = 0; l <= UPSIDE_L; l++) {
|
|
int j = stack.size() - 1 - (1 << l);
|
|
if (j < 0) {
|
|
break;
|
|
}
|
|
upside[vv][l] = stack.get(j);
|
|
}
|
|
treefyDfs(vv, stack);
|
|
|
|
stack.remove(stack.size() - 1);
|
|
}
|
|
|
|
if (vertexTreeId[v] != vertexTreeId[vv] && vertexTreeId[vv] != -1) {
|
|
treeEgressPointsSet.add(v);
|
|
treeEgressPointsSet.add(vv);
|
|
}
|
|
}
|
|
|
|
dfsOut[v] = timer++;
|
|
}
|
|
|
|
void egressDijkstra(int origin, long[] distances) {
|
|
PriorityQueue<long[]> queue = new PriorityQueue<>(new Comparator<long[]>() {
|
|
@Override
|
|
public int compare(long[] o1, long[] o2) {
|
|
return Long.compare(o1[0], o2[0]);
|
|
}
|
|
});
|
|
Arrays.fill(tainted, false);
|
|
|
|
int treeId = vertexTreeId[origin];
|
|
|
|
queue.add(new long[]{0L, origin});
|
|
tainted[origin] = true;
|
|
|
|
while (!queue.isEmpty()) {
|
|
int v = (int) queue.poll()[1];
|
|
|
|
int[] dest = edges2Dest.get(v);
|
|
long[] dist = edges2Dist.get(v);
|
|
|
|
for (int i = 0; i < dest.length; i++) {
|
|
int vv = dest[i];
|
|
long c = dist[i];
|
|
|
|
distances[vv] = Math.min(distances[vv], distances[v] + c);
|
|
|
|
if (tainted[vv]) {
|
|
continue;
|
|
}
|
|
|
|
tainted[vv] = true;
|
|
queue.add(new long[]{distances[vv], vv});
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
|
|
void treefy() {
|
|
for (int v = 0; v < n; v++) {
|
|
if (vertexTreeId[v] == -1) {
|
|
Arrays.fill(tainted, false);
|
|
|
|
int treeId = treeCount;
|
|
treeCount++;
|
|
vertexTreeId[v] = treeId;
|
|
vertexTreeHeight[v] = 0;
|
|
vertexTreeLength[v] = 0;
|
|
|
|
List<Integer> stack = new ArrayList<>();
|
|
stack.add(v);
|
|
|
|
treefyDfs(v, stack);
|
|
}
|
|
}
|
|
}
|
|
}
|