Python3(3.9) 解法, 执行用时: 1765ms, 内存消耗: 31856K, 提交时间: 2021-04-23 13:29:30

T = int(input())
while T:
    T -= 1
    ans = 0    
    N = int(input())
    p = list(map(int,input().split(' ')))
    for i in range(N):
        p[i] -= 1
    w = list(map(int,input().split(' ')))
    allmin = min(w)
    vis = [0] * N
    for i in range(N):
        if vis[i] == 0:
            j = i
            cnt = 0
            sumnow = 0
            nowMin = float('inf')
            while vis[j] == 0:
                vis[j] = 1
                cnt += 1
                sumnow += w[j]
                nowMin = min(nowMin,w[j])
                j = p[j]
            ans += min(sumnow + (cnt - 2) * nowMin, sumnow + nowMin + (cnt + 1) * allmin)
    print(ans)            

C++(clang++11) 解法, 执行用时: 208ms, 内存消耗: 1072K, 提交时间: 2021-04-10 19:47:45

#include <stdio.h>
#include <algorithm>
#include <vector>
#define MN 100000

int n,a[MN+5],w[MN+5];

void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	int ans = 0;
	int minw = 233;
	for(int i=1;i<=n;i++)
		minw = std::min(minw,w[i]);
	for(int i=1;i<=n;i++){
		if(!w[i]) continue;
		int p = i;
		int tot = 0;
		int lminw = 233;
		int cnt = 0;
		do{
			tot += w[p];
			lminw = std::min(lminw,w[p]);
			w[p] = 0;
			cnt++;
			p = a[p];
		}while(p!=i);
		ans += std::min((cnt-2)*lminw+tot,minw*(cnt+1)+tot+lminw);
	}
	printf("%d\n",ans);
}

int main(){
	int T; scanf("%d",&T);
	while(T--) solve();
}