Problem:
Minimum Cost Sort You are given $n$ integers $w_i (i = 0, 1, ..., n-1)$ to be sorted in ascending order. You can swap two integers $w_i$ and $w_j$. Each swap operation has a cost, which is the sum of the two integers $w_i + w_j$. You can perform the operations any number of times. Write a program which reports the minimal total cost to sort the given integers. Input In the first line, an integer $n$ is given. In the second line, $n$ integers $w_i (i = 0, 1, 2, ... n-1)$ separated by space characters are given. Output Print the minimal cost in a line. Constraints  $1 \leq n \leq 1,000$  $0 \leq w_i\leq 10^4$  $w_i$ are all different  Sample Input 1 5
1 5 3 4 2 Sample Output 1 7 Sample Input 2 4
4 3 2 1 Sample Output 2 10

Solution (Python):
import bisect


def sorted_index(A):
    
    A_ = sorted(A)
    B = []
    for a in A:
        idx = bisect.bisect_left(A_, a)
        B.append(idx)
    return B


def cyclic_factorize(A):
    
    B = sorted_index(A)
    checked = [False] * len(A)
    cycle_lst = []
    for i, a in enumerate(A):
        if checked[i]:
            continue
        now = i
        checked[now] = True
        cycle = [a]
        next = B[now]
        while not checked[next]:
            now = next
            next = B[now]
            cycle.append(A[now])
            checked[now] = True
        cycle_lst.append(cycle)
    return cycle_lst


N = int(input())
*W, = map(int, input().split())
cycle_lst = cyclic_factorize(W)
ans = 0
global_min = min(W)
for cycle in cycle_lst:
    l = len(cycle)
    s = sum(cycle)
    local_min = min(cycle)
    ans += s + min((l - 2) * local_min, local_min + (l + 1) * global_min)
print(ans)

Solution (Python):
N = int(input())
*W, = map(int, input().split())
C = {w: i for i, w in enumerate(W)}
W.sort()

ans = 0
S = []
used = [0]*N
for i in range(N):
    if used[i]:
        continue
    sq = []
    w = W[i]
    p = i; j = None
    while j != i:
        j = C[w]; w = W[j]
        used[j] = 1
        sq.append(w)
        p = j
    mi = min(sq); ln = len(sq)
    if ln >= 2:
        ans += sum(sq)
    S.append((mi, ln))
S.sort()
m, ln = S[0]
if ln >= 2:
    ans += (ln-2)*m
for mi, ln in S[1:]:
    if ln <= 2:
        continue
    ans += min(m+mi+ln*m, (ln-2)*mi)
print(ans)

Solution (Python):
WMAX = 10**4 + 1
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)
is_visited = [False] * n  
next_idxs = {}  
for i, b in enumerate(B):
    next_idxs[b] = i

m_A = min(A)  




ans = 0
for i in range(n):
    if is_visited[i]:
        continue  
    cur = i  
    S = 0  
    n2 = 0
    m = WMAX  
    while True:
        
        is_visited[cur] = True
        S += A[cur]
        m = min(m, A[cur])
        n2 += 1
        
        cur = next_idxs[A[cur]]
        if is_visited[cur]:
            break  
    
    
    ans += min(m*(n2-2)+S, m+S+(1+n2)*m_A)

print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
c = 0
for i in range(n):
    x = a.index(b[i])
    j = 0
    while x > i:
        j += 1
        y = a.index(b[x])
        c += a[y]
        a[x],a[y] = a[y],a[x]
        
        
        x = y
    c += min(b[i]*j,b[i]*2+b[0]*(j+2))
print(c)

Solution (Python):
def minimum_cost_sort():
    sorted_positions = {str(val):i for i, val in enumerate(sorted(W))}
    is_passed = [False]*n
    minimum_weight = min(W)
    ans = 0
    for i in range(n):
        if is_passed[i]:
            continue
        pointer = i
        total_weight = 0
        local_minimum_weight = 10000
        counter = 0
        while not is_passed[pointer]:
            is_passed[pointer] = True
            total_weight += W[pointer]
            local_minimum_weight = min(local_minimum_weight, W[pointer])
            pointer = sorted_positions[str(W[pointer])]
            counter += 1
        ans += min(total_weight+local_minimum_weight*(counter-2), total_weight+minimum_weight*(counter+1)+local_minimum_weight)
    print(ans)

if __name__ == "__main__":
    n = int(input())
    W = list(map(int, input().split()))
    minimum_cost_sort()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)
m_A = B[0]

next_idxs = {}
for i in range(n):
    next_idxs[B[i]] = i

ans = 0
is_visited = [False] * n

for i in range(n):
    if is_visited[i]:
        continue
    cur = i
    S = 0
    n2 = 0
    m = A[i]
    while True:
        is_visited[cur] = True
        S = S + A[cur]
        m = min(m, A[cur])
        n2 = n2 + 1
        cur = next_idxs[A[cur]]
        if is_visited[cur]:
            break
    ans = ans + min(m*(n2-2)+S, m + S + (n2+1)*m_A)

print(ans)

Solution (Python):
def minimum_cost(A, m, k):
    """整数列 A を最小コストソートでソートした場合の総コストを返す。

    A 内の整数は 0 <= <= k のすべて異なる整数であり、
    m がその中で最小の数。
    """
    
    C = [0 for _ in range(0, k + 1)]
    for x in A:
        C[x] += 1
    
    
    C[0] -= 1
    for i in range(1, k + 1):
        C[i] += C[i - 1]

    total_cost = 0
    n = len(A)
    for i in range(n):
        j = i
        length = 0
        sum_weight = 0
        cur_min = k + 1
        while C[A[j]] >= 0:
            length += 1
            sum_weight += A[j]
            if A[j] < cur_min:
                cur_min = A[j]
            z = C[A[j]]
            C[A[j]] = -1
            j = z
        if length >= 3:
            if cur_min > m:
                total_cost += min(sum_weight + cur_min * (length - 2),
                                  (sum_weight - cur_min) + m * (length - 1) + 2 * (m + cur_min))
            else:
                total_cost += sum_weight + cur_min * (length - 2)
        elif length == 2:
            total_cost += sum_weight

    return total_cost

if __name__ == '__main__':
    import sys

    n = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    print(minimum_cost(A, min(A), max(A)))

Solution (Python):
def min_cost(nums, n):
    sorted_list = sorted(nums)
    global_min = sorted_list[0]
    check_list = [False] * n
    cost = 0
    for start_idx in range(n):
        if check_list[start_idx]:
            pass
        else:
            start_num = nums[start_idx]
            cycle_idx = start_idx
            cycle_count = 0
            min_num = start_num
            w_sum = 0
            while True:
                check_list[cycle_idx] = True
                cycle_num = nums[cycle_idx]
                w_sum += cycle_num
                next_idx = sorted_list.index(cycle_num)
                min_num = min(min_num, cycle_num)
                if next_idx == start_idx:
                    break
                cycle_idx = next_idx
                cycle_count += 1
            if cycle_count >= 1:
                cost1 = w_sum + (cycle_count - 1) * min_num
                cost2 = w_sum + min_num + (cycle_count + 2) * global_min
                cost += min(cost1, cost2)
    return cost


def main():
    n = int(input())
    nums = list(map(int, input().split(" ")))
    cost = min_cost(nums, n)
    print(cost)


if __name__ == "__main__":
    main()

Solution (Python):
import copy

def solve():
    ans = 0
    V = [False] * n
    B = sorted(A)
    maxWeight = B[-1]
    minWeight = B[0]
    T = [None] * (maxWeight + 1)
    for i in range(n):
        T[B[i]] = i
        
    for i in range(n):
        if V[i]:
            continue
        
        cur = i
        S = 0
        m = maxWeight
        an = 0
        while True:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
            if V[cur]:
                break
        ans += min(S + (an - 2) * m, m + S + (an + 1) * minWeight)
    
    return ans

n = int(input())
A = list(map(int, input().split()))

ans = solve()
print(ans)

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def update(j, min_w, sum_w, wn):
        j = ia[j][0]
        fin[j] = True
        w = ia[j][1]
        if w < min_w: min_w = w
        return j, min_w, sum_w + w, wn + 1

    inf = 10 ** 16
    n = int(input())
    aa = list(map(int, input().split()))
    ia = [[i, a] for i, a in enumerate(aa)]
    ia.sort(key=lambda x: x[1])
    
    fin = [False] * n
    min_a = ia[0][1]
    ans = 0
    for i in range(n):
        if fin[i]: continue
        min_w = inf
        sum_w = 0
        wn = 0

        j, min_w, sum_w, wn = update(i, min_w, sum_w, wn)
        if i == j: continue

        while j != i:
            j, min_w, sum_w, wn = update(j, min_w, sum_w, wn)

        ans += min(sum_w + min_w * (wn - 2), sum_w + min_a * (wn + 1) + min_w)
    print(ans)

main()

Solution (Python):
import copy
MAX_LENGTH = 1000
MAX_WEIGHT = 10001


def minimum_sort_cost(A):
    cost = 0
    n = len(A)
    s = min(A)
    B = sorted(A)
    V = [False] * n
    T = [None] * MAX_WEIGHT

    for i in range(n):
        T[B[i]] = i
    
    for i in range(n):
        if V[i]:
            continue

        cur = i
        circle_len = 0
        min_weight = MAX_WEIGHT
        circle_weight = 0

        while(True):
            V[cur] = True
            circle_len += 1
            weight = A[cur]
            min_weight = min(min_weight, weight)
            circle_weight += weight
            cur = T[weight]

            if V[cur]:
                break
        
        cost += min(circle_weight + (circle_len - 2) * min_weight,\
             min_weight + circle_weight + (circle_len + 1) * s)
    
    return cost


if __name__ == "__main__":
    n = int(input())
    *A, = map(int, input().split())
    print(minimum_sort_cost(A))

Solution (Python):

def solve(A, N):
    answer = 0

    B = list(A)
    V = [False] * N
    T = [None] * 10001
    s = min(A)

    B.sort()

    
    

    for i in range(N):
        T[B[i]] = i

    for i in range(N):
        if V[i] is True:  
            continue

        cur = i  
        S = 0
        m = 10000  
        an = 0  

        while True:
            V[cur] = True  
            an += 1  
            v = A[cur]  
            m = min(m, v)  
            S += v  
            cur = T[v]  
            if V[cur]:  
                break  

        
        
        
        
        

        answer += min(S + (an - 2) * m, m + S + (an + 1) * s)

    return answer


N = int(input())
A = list(map(int, input().split()))

answer = solve(A, N)
print(answer)

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
b=sorted(a)
c=0
for i in range(n-1):
    t,cnt=0,0
    x=a.index(b[i])
    while x!=i:
        y=a.index(b[x])
        a[x],a[y]=b[x],b[i]
        t+=b[x]+b[i]
        cnt+=1
        x=y
    if cnt:
        c+=min(t,(b[i]+b[0])*2+t-(b[i]-b[0])*cnt)
print(c)

Solution (Python):
n = int(input())
W = list(map(int,input().split()))
W_2 = W[:]
sorted_W = sorted(W)
cost = 0
for i in range(n):
    if i==0:
        while W[i]!=sorted_W[i]:
            a=W.index(sorted_W[i])
            b=W.index(sorted_W[a])
            W[a],W[b]=W[b],W[a]
            W_2[a],W_2[b]=W_2[b],W_2[a]
            cost+=W[a]+W[b]
    else:
        cost1=0
        cost2=0
        while W[i]!=sorted_W[i]:
            a=W.index(sorted_W[i])
            b=W.index(sorted_W[a])
            W[a],W[b]=W[b],W[a]
            cost1+=W[a]+W[b]
        c = W_2.index(sorted_W[i])
        W_2[0],W_2[c]=W_2[c],W_2[0]
        cost2+=W_2[0]+W_2[c]
        while W_2[0]!=sorted_W[0]:
            a=W_2.index(sorted_W[0])
            b=W_2.index(sorted_W[a])
            W_2[a],W_2[b]=W_2[b],W_2[a]
            cost2+=W_2[a]+W_2[b]
        if cost1<=cost2:
            W_2=W[:]
            cost+=cost1
        else:
            W=W_2[:]
            cost+=cost2
print(cost)

Solution (Python):
n = int(input())
w = list(map(int, input().split()))
b = w[:]
w.sort()
s = w[0]

class Solve():
    def __init__(self, w, b, s):
        self.w = w
        self.b = b
        self.s = s
        self.ans = 0
        self.v = [0] * n
    
    def sort(self):
        T = [0] * 10001
        for i in range(n):
            T[self.w[i]] = i
        for i in range(n):
            if self.v[i]:
                continue
            cur = i
            S = 0
            m = 10001
            an = 0
            while 1:
                self.v[cur] = 1
                an += 1
                l = self.b[cur]
                m = min(m, l)
                S += l
                cur = T[l]
                if self.v[cur]:
                    break
            self.ans += min(S + (an - 2) * m, S + m +(an + 1) * self.s)
        return self

cost = Solve(w, b, s).sort()
print(cost.ans)

Solution (Python):



WMAX = 10**4 + 1
n = int(input())
A = list(map(int, input().split()))
B = sorted(A)
is_visited = [False] * n  
next_idxs = {}  
for i, b in enumerate(B):
    next_idxs[b] = i

m_A = min(A)  




ans = 0
for i in range(n):
    if is_visited[i]:
        continue  
    cur = i  
    S = 0  
    n2 = 0
    m = WMAX  
    while True:
        
        is_visited[cur] = True
        S += A[cur]
        m = min(m, A[cur])
        n2 += 1
        
        cur = next_idxs[A[cur]]
        if is_visited[cur]:
            break  
    
    
    ans += min(m*(n2-2)+S, m+S+(1+n2)*m_A)

print(ans)

Solution (Python):
VMAX = 10000

def minCostSort(A, n):
	global VMAX
	VMIN = min(A)
	ans = 0
	B = A.copy()
	B.sort()
	T = [0] * (VMAX + 1)
	for i in range(n):
		T[B[i]] = i
	V = [False] * n
	for i in range(n):
		if V[i]:
			pass
		else:
			index = i
			minv = VMAX
			count = 0
			cycleweight = 0
			while 1:
				V[index] = True
				count += 1
				value = A[index]
				minv = min(minv, value)
				cycleweight += value
				index = T[value]
				if V[index]:
					break
			ans += min(cycleweight + (count - 2) * minv, cycleweight + minv + (count + 1) * VMIN)
	return ans


if __name__ == "__main__":
	n = int(input())
	A = list(map(int, input().split()))
	print(minCostSort(A, n))

Solution (Python):
def solve(n, A):
    def cycles():
        V = [False] * n
        B = sorted(A)
        T = {B[i]: i for i in range(n)}
        C = []

        for i in range(n):
            if V[i]:
                continue
            cur = i
            cycle = []
            while not V[cur]:
                V[cur] = True
                cycle.append(cur)
                cur = T[A[cur]]
            C.append(cycle)

        return C

    ans = 0
    s = min(A)

    for cycle in cycles():
        S = sum([A[i] for i in cycle])
        m = min([A[i] for i in cycle])
        an = len(cycle)
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)

    return ans


def main():
    n = int(input())
    A = [int(x) for x in input().split()]

    print(solve(n, A))


main()

Solution (Python):
n = int(input())
W = list(map(int, input().split()))

W_org = W[:]
W_org_idx = {w:i for i, w in enumerate(W_org)}
W_srt = list(sorted(W[:]))
W_srt_idx = {w:i for i, w in enumerate(W_srt)}







def rec(idx, ret):
    if W_org[idx] in ret:
        return ret
    
    ret.append(W_org[idx])
    idx = W_srt_idx[W_org[idx]]
    return rec(idx, ret)

ans = 0
searched = set()
all_min_r = min(W_org)
for i in range(n):    
    if W_org[i] in searched:
        continue
    ret = rec(i, [])
    for r in ret:
        searched.add(r)
    
    if len(ret) == 1:
        continue
    elif len(ret) == 2:
        ans += sum(ret)
    else:
        
        min_r = min(ret)
        ans_a = sum(ret) + len(ret)*min_r - 2*min_r
        
        ans_b = 2*(all_min_r+min_r) + (sum(ret)-min_r+all_min_r) + len(ret)*all_min_r - 2*all_min_r
        ans += min(ans_a, ans_b)

print(ans)

Solution (Python):

n = int(input())
A = list(map(int, input().split()))

B = sorted(A)

C = [0 for _ in range(n)]
CNT = 0
minA = B[0]

for i in range(n):
    
    if A[i] == B[i]:
        C[i] == 1
    
    elif C[i] == 0:
        cyc = []
        ind = i
        
        while C[ind] == 0:
            a = A[ind]
            cyc.append(a)
            C[ind] = 1
            ind = B.index(a)
        
        mincyc = min(cyc)
        cost1 = sum(cyc) + (len(cyc) - 2) * mincyc
        cost2 = sum(cyc) + mincyc + (len(cyc) + 1) * minA
        if cost1 > cost2:
            CNT += cost2
        else:
            CNT += cost1
    else:
        pass
print(CNT)

Solution (Python):
MAX = 1000
VMAX = 10000


def main():
    n = int(input())
    
    a_s = list(map(int, input().split(' ')))
    minimum = min(a_s)

    ans = 0

    t_s = [0] * (VMAX+1)
    b_s = [a for a in a_s]
    v_s = [False for _ in range(n)]
    b_s = sorted(b_s)

    for i in range(n):
        t_s[b_s[i]] = i

    for i in range(n):
        if v_s[i]:
            continue
        cur = i
        S = 0
        m = VMAX
        a_n = 0

        while True:
            v_s[cur] = True
            a_n += 1
            v = a_s[cur]
            m = min(m, v)
            S += v
            cur = t_s[v]
            if v_s[cur]:
                break
        ans += min(S + (a_n-2)*m, m+S+(a_n+1)*minimum)
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def calc_loop_cost(loop, min_w):
    if len(loop) == 1:
        return 0
    elif len(loop) == 2:
        return loop[0] + loop[1]
    else:
        cost1 = sum(loop) + (len(loop) - 2) * min(loop)
        cost2 = sum(loop) + min(loop) + (len(loop) + 1) * min_w
        return min(cost1, cost2)

n = int(input())
org_list = [int(s) for s in input().split()]
sorted_list = sorted(org_list)
check_list = [False] * n
loop_list = []
for i in range(n):
    if check_list[i]:
        continue

    loop = []
    check_list[i] = True
    loop.append(org_list[i])
    next_idx = sorted_list.index(org_list[i])
    while next_idx != i:
        check_list[next_idx] = True
        loop.append(org_list[next_idx])
        next_idx = sorted_list.index(org_list[next_idx])

    loop_list.append(loop)

min_w = sorted_list[0]
cost_sum = 0
for lp in loop_list:
    cost_sum += calc_loop_cost(lp, min_w)

print(cost_sum)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

B = sorted(A)
c = 0

for i in range(n-1):
    t = cnt = 0
    x = A.index(B[i])
    
    while x != i:
        y = A.index(B[x])
        A[x], A[y] = B[x], B[i]
        cnt += 1
        t += B[x] + B[i]
        x = y
    if cnt:
        c += min(t, (B[i]+B[0])*2+t-(B[i]-B[0])*cnt)
print(c)

Solution (Python):
n = int(input())
wlist = list(map(int,input().split()))
wdic = {j:i for i,j in enumerate(wlist)}
wlist.sort()
cost = 0
used = [0]*n
res = []
for i in range(n):
    storage = []
    if used[i]:
        continue 
    w = wlist[i]
    minimum = w
    used[i] = 1
    a = wdic[w]
    b = wlist[a]
    storage.append(w)
    while b not in storage:
        w = b
        used[a] = 1
        a = wdic[w]
        b = wlist[a]
        storage.append(w)
        
    ls = len(storage)
    cost += (sum(storage) - minimum)
    res.append((minimum,ls))
m,l = res[0]
if l>=2:
    cost += m*(l-1)
for minimum,ls in res[1:]:
    if ls>=2:
        cost += min(2*(m+minimum)+m*(ls-1), minimum*(ls-1))
    
print(cost)

Solution (Python):
input()
a=list(map(int,input().split()))
b=sorted(a)
c=0
for i in range(len(a)):
 x=a.index(b[i])
 j=0
 while x>i:
  j+=1
  y=a.index(b[x])
  c+=a[y]
  a[x],a[y]=a[y],a[x]
  x=y
 c+=min(b[i]*j,b[i]*2+b[0]*(j+2))
print(c)

Solution (Python):
if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))
    sorted_elements = sorted(elements)
    total_cost = 0

    for i in range(n - 1):
        cost = 0
        cnt = 0
        x_idx = elements.index(sorted_elements[i])
        while i != x_idx:
            y_idx = elements.index(sorted_elements[x_idx])
            elements[x_idx], elements[y_idx] = (sorted_elements[x_idx],
                                                sorted_elements[i])
            cnt += 1
            cost += sorted_elements[x_idx] + sorted_elements[i]
            x_idx = y_idx
        if cnt:
            total_cost += min(cost,
                              (sorted_elements[i] + sorted_elements[0]) * 2 + cost
                              - (sorted_elements[i] - sorted_elements[0]) * cnt)

    print(total_cost)

Solution (Python):
MAXV = 10**4

if __name__ == '__main__':
    n = int(raw_input())
    
    A = [0] + map(int, raw_input().split())
    
    
    
    C = [0 for i in range(MAXV + 1)]
    min_of_all = MAXV + 1

    for i in range(1, n + 1):
        C[A[i]] += 1
        min_of_all = min(min_of_all, A[i])

    for i in range(1, MAXV + 1):
        C[i] += C[i - 1]

    
    
    V = [0 for i in range(n + 1)]
    total_cost = 0
    for i in range(1, n + 1):
        if V[i] == 1:
            continue
        V[i] = 1  
        size_of_cycle = 1  
        min_of_cycle = A[i]
        sum_of_cycle = A[i]
        j = i  
        while True:
            j = C[A[j]]
            if i == j:
                break
            V[j] = 1
            size_of_cycle += 1
            sum_of_cycle += A[j]
            min_of_cycle = min(min_of_cycle, A[j])
        if size_of_cycle == 1:
            
            continue

        cost = sum_of_cycle + (size_of_cycle - 2) * min_of_cycle
        if min_of_all < min_of_cycle:
            
            diff = 2 * (min_of_all + min_of_cycle)
            
            diff += min_of_all - min_of_cycle
            
            diff += (size_of_cycle - 2) * (min_of_all - min_of_cycle)
            if diff < 0:
                cost += diff
        total_cost += cost

    print total_cost

Solution (Python):

n = int(input())
W = list(map(int, input().split()))



cost = 0
W_sorted = sorted(W)
W_min = W_sorted[0]

for i in range(n - 1):
    cycle_min = W_sorted[i]
    cost_cycle_in = 0
    cnt_change = 0

    index_cycle_min = W.index(cycle_min)

    while index_cycle_min != i:
        cycle_change = W_sorted[index_cycle_min]
        index_cycle_change = W.index(cycle_change)

        W[index_cycle_min], W[index_cycle_change] = cycle_change, cycle_min
        cost_cycle_in += cycle_min + cycle_change

        cnt_change += 1
        index_cycle_min = index_cycle_change

    if cnt_change:
        cost_cycle_out = (
            cost_cycle_in
          + (cycle_min + W_min) * 2
          - (cycle_min - W_min) * cnt_change
        )

        cost += min(cost_cycle_in, cost_cycle_out)



print(cost)

Solution (Python):
n = int(input())
W = [[int(i)] for i in input().split()]
for ni in range(n):
    W[ni].append(ni)
W.sort()
G = [[] for i in range(n)]
i = 0
j = 0
cnt = 0
D = []
while cnt < n:
    if W[i][0] in G[j]:
        j += 1
        while i in D:
            i += 1
    else:
        G[j].append(W[i][0])
        D.append(i)
        cnt += 1
        i = W[i][1]
group_num = j + 1
cost = 0
W_min = min([min(G[i]) for i in range(group_num)])
for gi in range(group_num):
    if len(G[gi]) > 1:
        if (min(G[gi])+W_min)*2 > (min(G[gi])-W_min)*(len(G[gi])-1):
            cost += sum(G[gi])+ (len(G[gi])-2)*min(G[gi])
        else:
            cost += sum(G[gi])-min(G[gi])+ (len(G[gi])-1)*W_min+(min(G[gi])+W_min)*2

print(cost)

Solution (Python):
def solve(A):
    correct_a = sorted(A)
    correct_index = {n: i for i, n in enumerate(correct_a)}
    ans, min_n = 0, correct_a[0]
    cycles = []
    used = [0]*len(A)
    for i in filter(lambda i: not used[i], range(len(A))):
        used[i] = 1
        cycle, next_i = [i], correct_index[A[i]]
        while next_i != i:
            cycle.append(next_i)
            used[next_i] = 1
            next_i = correct_index[A[next_i]]
        cycles.append(cycle)

    for cycle in cycles:
        if len(cycle) == 2:
            ans += correct_a[cycle[0]] + correct_a[cycle[1]]
        elif len(cycle) > 2:
            ans += (min(correct_a[cycle[0]]*(len(cycle)-1), correct_a[cycle[0]]*2 + min_n*(len(cycle)+1))
                    + sum(correct_a[i] for i in cycle[1:]))

    return ans


if __name__ == "__main__":
    input()
    a = list(map(int, input().split()))
    print(solve(a))

Solution (Python):
def minimumCostSort(arr, arr_size):
    cost = 0
    sortarr = sorted(arr)
    cyclecontainer = []
    for i in range(arr_size):
        cycle = [arr[i]]
        next = sortarr.index(arr[i])
        while arr[next] != arr[i]:
            cycle += [arr[next]]
            next = sortarr.index(arr[next])
        cycle = sorted(cycle)
        if cycle not in cyclecontainer:
            cyclecontainer.append(cycle)
            if len(cycle) == 1:
                pass
            elif len(cycle) == 2:
                cost += sum(cycle)
            elif len(cycle) >= 3:
                cost += min(sum(cycle)+((len(cycle)-2)*min(cycle)), sum(cycle)+min(cycle)+((len(cycle)+1)*min(arr)))
    return cost
n = int(input())
w = list(map(int, input().split()))
print(minimumCostSort(w, n))

Solution (Python):
n = int(input())
n_lst = list(map(int, input().split()))
sorted_lst = sorted(n_lst)
cost = 0

for i in range(n):
    a = n_lst.index(sorted_lst[i])
    j = 0
    while a > i:
        j += 1
        b = n_lst.index(sorted_lst[a])
        cost += n_lst[b]
        n_lst[a],n_lst[b] = n_lst[b],n_lst[a]
        a = b
    cost += min(sorted_lst[i]*j,sorted_lst[i]*2+sorted_lst[0]*(j+2))
print(cost)

Solution (Python):


n = int(input())
*w, = map(int, input().split())
s = list(sorted(w))

si = [0] * 10001
for i, v in enumerate(s):
    si[v] = i

ans = 0
b = [False] * n
for i in range(n):
    if b[i]:
        continue
    j = i
    mw = w[i]
    z = 0
    nn = 0
    while b[j] == False:
        b[j] = True
        nn += 1
        mw = min(w[j], mw)
        z += w[j]
        j = si[w[j]]
    c = min((nn - 2) * mw + z, mw + z + (nn + 1) * s[0])
    ans += c

print(ans)

Solution (Python):


n = int(input().rstrip())
wi = [int(i) for i in input().rstrip().split()]
visited = [False for i in range(n)]
minw = min(wi)
dict = {}
for i, v in enumerate(sorted(wi)):
    dict[v] = i

ans = 0
for i in range(n):
    if visited[i]:
        continue
    cnt = 0
    now = i
    mi = 100000
    s = 0
    while True:
        if visited[now]:
            break
        cnt += 1
        visited[now] = True
        mi = min(mi, wi[now])
        s += wi[now]
        now = dict[wi[now]]
    
    tmp = s + (cnt-2)*mi
    tmp = min(tmp, s+mi+minw*(cnt+1))
    ans += tmp

print(ans)

Solution (Python):
from sys import stdin

W_MAX = 10000

n = int(stdin.readline().rstrip())
w = [int(x) for x in stdin.readline().rstrip().split()]
min_w = min(w)
idx = {}
for i, wi in enumerate(sorted(w)):
    idx[wi] = i

isVisited = [False]*n
cost = 0
for i in range(n):
    if isVisited[i]:
        continue

    cur = i
    cyc = []
    min_cyc = W_MAX
    while not isVisited[cur]:
        isVisited[cur] = True
        cyc.append(w[cur])
        min_cyc = min(min_cyc, w[cur])
        cur = idx[w[cur]]

    cost += min(sum(cyc) + (len(cyc)-2)*min_cyc, sum(cyc) + (len(cyc)+1)*min_w + min_cyc)

print(cost)

Solution (Python):
def silly_sort(target):
    ranked = sorted(target)
    length = len(target)
    rings = [n for n in range(length)]
    all_cost = 0
    minimum = ranked[0]
    base_index = {}
    rank_index = {}
    for i, (t, r) in enumerate(zip(target, ranked)):
        base_index[t] = i
        rank_index[r] = i
    for i in range(length):
        if rings[i] != -1 and target[i] != ranked[i]:
            ring_sum = target[i]
            min_m = target[i]
            num_ring = 1
            next_index = rank_index[target[i]]
            next_num = target[next_index]
            while next_index != i:
                
                num_ring += 1
                ring_sum += next_num
                min_m = min(min_m, next_num)
                rings[next_index] = -1
                next_index = rank_index[target[next_index]]
                next_num = target[next_index]
            
            all_cost += min((ring_sum + min_m * (num_ring - 2) ), (ring_sum + min_m + minimum * (num_ring + 1) ) )
        rings[i] = -1
    return all_cost

l = int(input())
t = [int(n) for n in input().split(" ")]
print(silly_sort(t))

Solution (Python):
def solve(a,n,mn,mx):
	ans=0
	V=[False]*n
	b=sorted(a)
	T=[0]*(mx+1)
	for i in range(n): T[b[i]]=i
	for i in range(n):
		if V[i]: continue
		cur=i
		sum=0
		cnt=0
		m=1<<30
		while True:
			V[cur]=True
			v=a[cur]
			cnt+=1
			sum+=v
			m=min(m,v)
			cur=T[v]
			if V[cur]: break
		ans+=min(sum+(cnt-2)*m,sum+m+(cnt+1)*mn)
	return ans

n=int(input())
a=list(map(int,input().split()))
mn=1<<30
mx=mn*-1
for i in range(n):
	mn=min(mn,a[i])
	mx=max(mx,a[i])
print(solve(a,n,mn,mx))

Solution (Python):
def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    sorted_array = sorted(array)

    groups = []
    for i in range(len(array)):
        moving_src_val = array[i]
        if not moving_src_val:
            continue
        group = [moving_src_val]
        while True:
            moving_tgt_idx = sorted_array.index(moving_src_val)
            moving_tgt_val = array[moving_tgt_idx]
            if moving_tgt_val in group:
                break
            group.append(moving_tgt_val)
            array[moving_tgt_idx] = False
            moving_src_val = moving_tgt_val
        array[i] = False
        groups.append(group)

    

    min_cost = 0
    min_in_array = sorted_array[0]
    for group in groups:
        n_group = len(group)
        if n_group == 1:
            continue
        min_in_group = min(group)
        sum_without_min = sum(group) - min_in_group

        cost1 = (n_group - 1) * min_in_group
        cost2 = (n_group + 1) * min_in_array + 2 * min_in_group

        if cost1 < cost2:
            min_cost += cost1 + sum_without_min
        else:
            min_cost += cost2 + sum_without_min

    print(min_cost)
    return


main()

Solution (Python):
n=int(input())
data=list(map(int,input().split()))

sorted_data=sorted(data)
mindata=sorted_data[0]

data_dict={}
for i in range(n):
    data_dict[data[i]]=i

sorted_data_dict={}
for i in range(n):
    sorted_data_dict[sorted_data[i]]=i


swap_cost=0


for x in sorted_data:
    if(sorted_data_dict[x]!=data_dict[x]):
        tmp_cost=0
        swap_num=0

        while(sorted_data_dict[x]!=data_dict[x]):
            ind1=data_dict[x]
            ind2=data_dict[sorted_data[ind1]]
            data_dict[x]=ind2
            data_dict[sorted_data[ind1]]=ind1
            tmp_cost+=x+sorted_data[ind1]
            swap_num+=1
        if( (x+mindata)*2 < swap_num*(x-mindata) ):
            tmp_cost+=(x+mindata)*2 - swap_num*(x-mindata)
        swap_cost+=tmp_cost

print(swap_cost)

Solution (Python):
N = int(input())
*W, = map(int, input().split())
C = {w: i for i, w in enumerate(W)}
W.sort()

ans = 0
S = []
used = [0]*N
for i in range(N):
    if used[i]:
        continue
    sq = []
    w = W[i]
    p = i; j = None
    while j != i:
        j = C[w]; w = W[j]
        used[j] = 1
        sq.append(w)
        p = j
    mi = min(sq); ln = len(sq)
    if ln >= 2:
        ans += sum(sq)
    S.append((mi, ln))
S.sort()
m, ln = S[0]
if ln >= 2:
    ans += (ln-2)*m
for mi, ln in S[1:]:
    if ln <= 2:
        continue
    ans += min(m+mi+ln*m, (ln-2)*mi)
print(ans)

Solution (Python):
import sys

n = int(sys.stdin.readline())
w = list(map(int, sys.stdin.readline().split()))
c = [False]*n
u = sorted(w)
cost = 0
while False in c:
    i = c.index(False)
    c[i] = True
    i0=i
    llen=1
    lmin=w[i]
    while True:
        i = u.index(w[i])
        if c[i]: break
        c[i] = True
        llen+=1
        if lmin > w[i]: lmin = w[i]
        cost += w[i]

    if llen>1:
        cost += w[i0]+min(lmin+(llen+1)*min(w), lmin*(llen-2))

print(cost)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
c = 0
for i in range(n - 1):
    t = cnt = 0
    
    x = a.index(b[i])
    while x != i:
        
        y = a.index(b[x])
        
        a[x], a[y] = a[y], a[x]
        cnt += 1
        
        t += a[x] + a[y]
        x = y
    if cnt:
        c += min(t, (b[i] + b[0]) * 2 + t - (b[i] - b[0]) * cnt)
print(c)