我們給出了一個靜態圖的N節點，在那里我們有邊緣下面給出：
1. node-1 to node-i (for all 2 <= i <= N) of weight N 1.
2. node-x to node-y (for all 2 <= x,y <= N) of weight 1, if and only if x divides y OR y divides x.
我們得到Q了型別的查詢，(u, v)我們需要找到節點u和節點之間的最短路徑v.
約束：
T <= 10^5 // number of test cases
N <= 2 * 10^5 // number of nodes
Q <= 2 * 10^5 // number of queries
u,v <= N
方法：幾乎恒定的時間 - O(1)。
private int gcd(int x, int y) {
if(x % y == 0) return y;
return gcd(y, x % y);
}
private int lcm(int x, int y) {
return (x * y) / gcd(x, y);
}
private int[] shortest_path(int N, int Q, int[][] queries) {
int[] result = new int[Q];
int[] smallestDivisor = new int[N 1];
for(int i = 2; i <= N; i ) {
if(smallestDivisor[i] == 0) {
int f = 1;
while(i * f <= N) {
if(smallestDivisor[i * f] == 0)
smallestDivisor[i*f] = i;
f = 1;
}
}
}
for(int i = 0; i < Q; i ) {
int u = queries[i][0];
int v = queries[i][1];
int LCM = lcm(u, v);
int GCD = gcd(u, v);
int smallestDivisorOfU = smallestDivisor[u];
int smallestDivisorOfV = smallestDivisor[v];
if(u == v)
result[i] = 0; // if nodes are same
else if(u == 1 || v == 1)
result[i] = N 1; // if any of the node is '1'
else if(u % v == 0 || v % u == 0)
result[i] = 1; // if nodes are divisible
else if(GCD != 1 || LCM <= N)
result[i] = 2; // if gcd != 1 || lcm exists thus we can go as: 'x' --> gcd(x, y)/lcm(x,y) --> 'y' : 2 distance
else if(Math.min(smallestDivisorOfU * v, smallestDivisorOfV * u) <= N)
result[i] = 3;
else
result[i] = 2 * (N 1); // we have to go via '1' node
}
return result;
}
這種方法是否適用于每個測驗用例？
uj5u.com熱心網友回復：
在 LCM 之前添加 GCD claculation 以提供路徑
A => GCD(A,B) => B（完成）當 LCM 檢查失敗時，對值進行因式分解。如果它們是素數，則通過
"1"節點移動。否則檢查
if (min(SmallestDivisorOfA * B , SmallestDivisorOfB * A) <= N)
result[i] = 3;
Example: 7=>14=>2=>6
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/382609.html
上一篇：最少斷線次數
下一篇：如何“加入”二次或三次樣條？