Subtask 2

Vì $a_i=a_j$ nên trọng số các cạnh ban đầu bằng $2$ do đó ta chỉ cần quan tâm các cạnh thêm vào có trọng số bằng $1$ là được.

Subtask 3,4

Ta xây đồ thị $2$ phía. Bên trái là $n$ đỉnh đã cho. Bên phải là ${10}^5$ đỉnh giả. Thêm cạnh nối giữa đỉnh $u$ bên trái và đỉnh $v$ bên phải với trọng số $\frac{a_u}{v}$ nếu $a_u$ chia hết cho $v$.

Nhận xét: Đường đi ngắn nhất của đồ thị gốc bằng đường đi ngắn nhất của đồ thị mới

Chứng minh:

Đặt $d$ là $1$ ước chung của $a_u$ và $a_v$. Kí hiệu $(u,v,w)$ là một cạnh nối giữa đỉnh $u$ bên trái và đỉnh $v$ bên phải với trọng số $w$.

Trong đồ thị $2$ phía, cạnh $(u,d,\frac{a_u}{d})$ và $(v,d,\frac{a_v}{d})$ đều tồn tại, do đó tồn tại đường đi từ $u$ tới $v$ có tổng trọng số là $(a_u+a_v)/d$ với $d$ là $1$ ước chung bất kì. Trong tất cả các giá trị có thể của $d$, dễ dàng thấy rằng $d=gcd(a_u,a_v)$ là tạo ra trọng số nhỏ nhất.

Do đó, $1$ cách đi từ $u$ tới $v$ mà chỉ sử dụng các đỉnh giả trung gian trong đồ thị mới có trọng số không nhỏ hơn $(a_u+a_v)/gcd(a_u,a_v)$. Vì vậy nếu trong đường đi ngắn nhất của đồ thị mới có đoạn đi từ $u$ tới $v$ chỉ qua các đỉnh giả trung gian thì chắc chắn tổng trọng số của quãng này là $(a_u+a_v)/gcd(a_u,a_v)$, hay chính là tương ứng với việc đi trực tiếp từ đỉnh $u$ tới đỉnh $v$ trong đồ thị gốc. -> dpcm

Mỗi đỉnh $u$ bên trái có [số ước của $a_u$] cạnh nối sang phải. Các đỉnh có cùng trọng số thì chập vào làm một (do độ dài đường đi ngắn nhất là bằng nhau). Đặt $A=max(a_i)$. Khi đó tổng số cạnh nối là: số ước của $1$ + số ước của $2$ + … + số ước của $A$ = $A\times log(A)$.

Subtask 5

Ở subtask trước, ta chập các đỉnh chung trọng số vào làm $1$ để thu được đồ thị có $A\times log(A)$ cạnh.

Ở subtask này, ta chỉ chập các đỉnh có chung trọng số nếu như chúng không phải đầu mút của cạnh nào trong $m$ cạnh được thêm vào.

Nếu như có đỉnh $u$ là đầu mút của $1$ cạnh nào đó trong $m$ cạnh thêm vào, đồng thời cũng có $1$ đỉnh bất kì nào đó có cùng trọng số với $u$, ta sẽ xây thêm [số ước của $a_u$] cạnh nữa nối từ đỉnh $u$ (bên trái) tới các đỉnh ước của nó ở bên phải và xây các cạnh nhận $u$ làm đầu mút trong $m$ cạnh được thêm với cách đỉnh tương ứng bên trái (như vậy đồ thị không còn là đồ thị $2$ phía nữa nhưng vẫn bảo đảm được tính chất của đường đi ngắn nhất)

Khi đó, số cạnh được thêm vào là $m\times$ [số ước của $A$] $+m$. Do $a_i\le {10}^5$ nên nó có tối đa $65$ ước nên số cạnh thêm vào là $66\times m$.

Vậy tổng số cạnh bây giờ là $A\times log(A)+66\times m$.

Độ phức tạp của Dijkstra là: $O((A\times log(A)+66m)\times log(n))$