Kamui

发布时间: 2017年12月10日 22:14   最后更新: 2017年12月10日 22:18   时间限制: 4000ms   内存限制: 512M

In order to fight Life Battle-Fibers, little G, the god of computer, created a mysterious organization, but this organization isn’t important in this problem. In addition to founding the organization, little G also studies various ways to fight Life Battle-Fibers.The most powerful weapon that he created is a kind of clothing named Kamui. Among all Kamui, Senketsu has the strongest power.

Little G now has the blueprint of Senketsu, but sewing Senketsu is very troublesome, which need to put different kinds of fibers in the correct position. The blueprint can be described by an permutation of integers from 1 to N, with different numbers representing different kinds of fibers. We use ‘A’ to represent this permutation. If the i-th number in A is j, then the j-th kind of fiber should be put in the i-th position. Little G initialy took out n kinds of fibers and placed the i-th kind of fiber in the i-th position. In order to change the fiber sequence to the same as the the blueprint of Senketsu, he can exchange fibers in any two positions any times. If we want to exchange the x-th kind and the y-th kind of fibers, then the exchange needs Wx+Wy units time. Given the array A and W, you need to tell little G the shortest time to complete Senketsu.

In the first line there is an integer T(1<=T<=3), which indicates the number of test cases.
For each test case, the first line is an integer representing N(1<=N<=10^6).
The second line consists of n integers, representing the array W(1<=Wi<=10^9).
The third line consists of n integers, representing the array A. It is guaranteed that A is a permutation of integers from 1 to N.

For each test case, print the answer in a line.

复制
2
4
1 2 1 2
2 1 4 3
6
1 5 5 5 5 5
1 3 4 5 6 2
6
36

The first case: swap position (1, 2), swap position (3, 4)

The second case: swap position (1,2)swap position (2,6)swap position (5,6)swap position (4,5)swap position (3,4)swap position (1,3).

2017 fdu-icpc

2017 Fudan ACM-ICPC 程序设计校赛现场赛