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):
VMAX = 10000
n = int(input())
A = list(map(int, input().split()))
s = min(A)
def solve():
    ans = 0
    V = [False] * n
    B = sorted(A)
    T = [0] * (VMAX + 1)
    for i in range(n):
        T[B[i]] = i
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = 0
        m = VMAX
        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) * s)
    return ans
print(solve())

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
s = min(A)
def solve():
    ans = 0
    V = [False] * n
    B = sorted(A)
    T = {B[i]: i for i in range(n)}
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = an = 0
        m = 10000
        while not V[cur]:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans
print(solve())

Solution (Python):
def decode():
    n = int(input())
    w = [int(x) for x in input().split()]

    return n, w


def search(w, sw, swi):
    wi = w.index(sw[swi])
    cost = 0
    count = 0
    while wi != swi:
        tw = sw[wi]
        ti = w.index(tw)
        w[ti], w[wi] = w[wi], w[ti]
        cost += w[ti] + w[wi]
        count += 1
        wi = ti
    return cost, count


def search_min_cost(w):
    sorted_w = list(w)
    sorted_w.sort()

    min_w = sorted_w[0]
    cost = 0

    for i, sww in enumerate(sorted_w):
        tmp_cost, count = search(w, sorted_w, i)
        cost += min(tmp_cost, tmp_cost + (min_w + sww) * 2 - (sww - min_w) * count)

    return cost


if __name__ == '__main__':

    n, w = decode()
    print(search_min_cost(w))

Solution (Python):
def calc_cost(hoge):
    cost = 0
    hoge_refer = sorted(hoge[:])
    
    checker = [False] * len(hoge)
    
    abs_min = hoge_refer[0]
    
    indexer = {hoge_refer[i]:i for i in range(len(hoge_refer))}
    
    for now_index in range(len(hoge)):
        if checker[now_index]:
            continue
        current = now_index
        size = 0
        sum_num = 0
        circle_min = 10 ** 4
        while True:
            checker[current] = True
            size += 1
            val = hoge[current]
            circle_min = min(circle_min, val)
            sum_num += val
            current = indexer[val]
            if checker[current]:
                break
        cost += min(sum_num+(size-2)*circle_min, circle_min+sum_num+(size+1)*abs_min)
    return cost
        
    
if __name__ == '__main__':
    _ = int(input())
    hoge = [int(x) for x in input().split()]
    print(calc_cost(hoge))

Solution (Python):
input()
w=list(map(int,input().split()))
x=min(w)
m={k:v for k,v in zip(sorted(w),w)if k!=v}
l=list(m.keys())
p=[]
while l:
 a=l.pop();b=m[a];l.remove(b)
 if a==m[b]:p+=[[a,b]]
 else:
  t=[b]
  while 1:
   c=m[b];t+=[c]
   if c==a:p+=[t];break
   else:b=c;l.remove(c)
n=0
for s in p:
 n+=sum(s);t=len(s);y=min(s)
 if t>2:n+=min((t-2)*y,y+(t+1)*x)
print(n)

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

Solution (Python):
import itertools
 
 
WAIT, PRESORT, SORTED = 0, 1, 2
cost = 0
 
def swap(w1, w2):
    global cost
    cost += w1[WAIT] + w2[WAIT]
    w1[PRESORT], w2[PRESORT] = w2[PRESORT], w1[PRESORT]
     
 
n = input()
w = [[wi, i, None] for i, wi in enumerate(map(int, input().split()))]
s = sorted(w)
minw = s[0]
for i, wi in enumerate (s):
    wi[SORTED] = i
     
for si in s:
    tmp = si
    t = []
    while tmp[SORTED] != si[PRESORT]:
        tmp = w[tmp[SORTED]]
        t += [tmp]
 
    if len(t ) and minw != si and si[WAIT] * (len(t) - 2) > minw[WAIT] * (len(t) + 2):
        swap(minw, si)
        for ti in t[::-1]:
            swap(minw, ti)
        swap(minw, si)
    else:
        for ti in t[::-1]:
            swap(si, ti)
     
print(cost)

Solution (Python):
input()
w=list(map(int,input().split()))
x=min(w)
m={k:v for k,v in zip(sorted(w),w)if k!=v}
l=list(m.keys())
n=0
while l:
 a=l.pop();b=m[a];l.remove(b)
 if a==m[b]:n+=a+b
 else:
  t=[b]
  while 1:
   c=m[b];t+=[c]
   if c==a:p,q=len(t),min(t);n+=sum(t)+min((p-2)*q,q+(p+1)*x);break
   else:b=c;l.remove(c)
print(n)

Solution (Python):
input()
w=list(map(int,input().split()))
s=sorted(w)
x=s[0]
m={k:v for k,v in zip(s,w)if k!=v}
l=list(m.keys())
n=0
while l:
 a=l.pop();b=m[a];l.remove(b)
 if a==m[b]:n+=a+b
 else:
  t=[b]
  while 1:
   c=m[b];t+=[c]
   if c==a:p,q=len(t),min(t);n+=sum(t)+min((p-2)*q,q+(p+1)*x);break
   else:b=c;l.remove(c)
print(n)

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

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

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

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

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):
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):
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):
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):
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):
def solve():
    ans = 0

    B = A[:]
    V = [False] * n

    B.sort()
    for i in range(n):
        T[B[i]] = i
    for i in range(n):
        if V[i]:
            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
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().split()]
    s = min(A)
    s = min(s, 10000)
    T = [0] * (max(A)+1)
    ans = solve()
    print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
cost = 0
for i in range(n):
    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:
        cost += min(t, (b[i] + b[0]) * 2 + t - (b[i] - b[0]) * cnt)
print(cost)

Solution (Python):


SENTINEL = 10**9 + 1


def merge_sort(alist):
    """Sort alist using mergesort.
    Returns a tuple of the number of comparisons and sorted list.

    >>> merge_sort([8, 5, 9, 2, 6, 3, 7, 1, 10, 4])
    (34, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    """
    def _sort(left, right):
        count = 0
        if left + 1 < right:
            mid = (left + right) // 2
            count += _sort(left, mid)
            count += _sort(mid, right)
            count += merge(left, mid, right)

        return count

    def merge(left, mid, right):
        count = 0
        ll = alist[left:mid] + [SENTINEL]
        rl = alist[mid:right] + [SENTINEL]

        i = j = 0
        for k in range(left, right):
            count += 1
            if ll[i] <= rl[j]:
                alist[k] = ll[i]
                i += 1
            else:
                alist[k] = rl[j]
                j += 1

        return count

    comp = _sort(0, len(alist))
    return (comp, alist)


def min_cost(li1, li2):
    """calculate minimum cost to transform li1 into li2.

    >>> min_cost([1, 5, 3, 4, 2], [1, 2, 3, 4, 5])
    7
    >>> min_cost([4, 3, 2, 1], [1, 2, 3, 4])
    10
    """
    def find_moves(i, j):
        start = i
        elems = [i]
        mincost = li1[i]
        minidx = 0

        while j != start:
            if mincost > li1[j]:
                mincost = li1[j]
                minidx = len(elems)
            elems.append(j)
            j = li2.index(li1[j])

        elems = elems[minidx+1:] + elems[:minidx+1]
        if 2 * (mincost + li1[mini]) < (len(elems) - 1) * (mincost - li1[mini]):
            elems.append(mini)
            elems.insert(0, mini)

        q = elems.pop()
        p = elems.pop()
        yield (p, q)
        while len(elems) > 0:
            q = p
            p = elems.pop()
            yield (p, q)


    def move(i, j):
        cost = 0
        for p, q in find_moves(i, j):
            li1[p], li1[q] = li1[q], li1[p]
            cost += li1[p] + li1[q]

        return cost

    assert len(li1) == len(li2)
    size = len(li1)
    totalcost = 0

    for i in reversed(range(size)):
        if li1[i] != li2[i]:
            mini = li1.index(li2[0])
            totalcost += move(li1.index(li2[i]), i)

    return totalcost


def run():
    _ = int(input())  
    li = [int(i) for i in input().split()]
    sli = li[:]
    (_, sli) = merge_sort(sli)

    print(min_cost(li, sli))


if __name__ == '__main__':
    run()

Solution (Python):
import copy
n = int(input())
a = list(map(int, input().split()))
b = copy.deepcopy(a)
b.sort()
loop = []
minp = min(a)
t = [0 for i in range(n)]
while True:
    i = t.index(0)
    j = len(loop)
    loop.append([a[i]])
    t[i] = 1
    while True:
        i = b.index(a[i])
        if t[i] == 1:
            break
        t[i] = 1
        loop[j].append(a[i])
    if sum(t) == n:
        break
    j += 1
cost = 0
for i in loop:
    if len(i) == 1:
        continue
    ps = sum(i)
    pl = len(i)
    pm = min(i)
    p1 = ps + (pl - 2) * pm
    p2 = ps + pm + (pl + 1) * minp
    cost += min(p1, p2)
print(cost)

Solution (Python):
def solve(A, n, s):
    ans = 0

    V = [False for i in range(n)] 
    B = sorted(A)
    T = [None for i in range(10001)]
    for i in range(n):
        T[B[i]] = i
    for i in range(n):
        if V[i]: 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
        ans += min(S + (an-2)*m, m+S+(an+1)*s)
    return ans

n = int(input())
A = list(map(int, input().split(' ')))
s = min(A)
ans = solve(A, n, s)
print(ans)

Solution (Python):

n = int(input())
A = list(map(int, input().split()))
B = A[:]
B.sort()
C = [True for i in range(n)]
minA = min(A)

j = 0
a = []
total = 0
for i in range(n):
    circle = []
    j = i
    while C[j]:
        C[j] = False
        j = B.index(A[j])
        circle.append(A[j])
    n_c = len(circle)
    if n_c == 2:
        total += (circle[0]+circle[1])
    if n_c > 2:
        minc = min(circle)
        cirSum = sum(circle)
        total += min( cirSum + (n_c-2) * minc , cirSum + minc + (n_c+1)*minA)
    a.append(circle)
    

print(total)

Solution (Python):
def make_cyclic(w, v):
    flags = [True] * len(w)

    cyclics = []
    for i in range(len(w)):
        if flags[i]:
            flags[i] = False
            cycle = [w[i]]
            now = w[i]
            while True:
                j = v.index(now)
                if j == i:
                    break
                cycle.append(w[j])
                now = w[j]
                flags[j] = False
            cyclics.append(cycle)

    return cyclics


def min_cost_sort(w):
    v = w.copy()
    v.sort()

    cyclics = make_cyclic(w, v)

    ans = 0
    for cycle in cyclics:
        inner_cycle = min(cycle) * (len(cycle) - 2) + sum(cycle)
        if len(set(w) - set(cycle)) >= 1:
            outer_cycle = min(cycle) + min(set(w) - set(cycle)) * (len(cycle) + 1) + sum(cycle)
        else:
            outer_cycle = inner_cycle + 1
        ans += min(inner_cycle, outer_cycle)

    return ans


n = int(input())
w = [int(x) for x in input().split()]

print(min_cost_sort(w))

Solution (Python):
import sys
input = sys.stdin.readline

def Solve():
    ans = 0
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S, an = 0, 0
        m = VMAX
        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) * s)
    return ans

MAX = 1000
VMAX = 10000

n = int(input())
A = [int(x) for x in input().split()]
s = min(A)
B = sorted(A)
T = [0] * (VMAX + 1)
for i, b in enumerate(B):
    T[b] = i
V =[False] * MAX
ans = Solve()
print(ans)

Solution (Python):
import math

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

MAX = max(A)
m = min(A)
B = A.copy()
result = 0

def merge(A, left, mid, right):

  global  count

  L = A[left:mid]
  L.append(math.inf)
  R = A[mid:right]
  R.append(math.inf)
  i = 0
  j = 0

  for k in range(left,right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1


def mergeSort(A,left,right):
    if left +1 < right:
        mid = (left+right) // 2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

mergeSort(B,0,n)

T = [None] * (MAX+1)
V = [False] * n
for i in range(n):
    T[B[i]] = i

for i in range(n):
    if V[i]: continue
    cur = i
    ant = 0
    S = 0
    s = MAX
    while(1):
        V[cur] = True
        v = A[cur]
        if v < s:
            s = v
        S += v
        ant += 1

        cur = T[v]
        if V[cur]: break

    result += min(S+(ant-2)*s,S+s+(ant+1)*m)


print(result)

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
    ai = A.index(B[i])  

    while ai != i:  
        y = A.index(B[ai])  
        A[ai], A[y] = B[ai], B[i]  
        cnt += 1
        t += B[ai] + B[i]  
        ai = 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()))
ws = sorted(w)
d = {v:i for i, v in enumerate(ws)}
checked = [False] * n
cost = 0
wmin = min(w)

for i in range(n):
    if checked[i] or d[w[i]] == i:
        continue
    
    gcnt = 0
    gmin = gtot = w[i]
    nexti = d[w[i]]
    while nexti != i:
        checked[nexti] = True
        gcnt += 1
        gmin = min(gmin, w[nexti])
        gtot += w[nexti]
        nexti = d[w[nexti]]
    cost += gtot + min(gmin * (gcnt - 1), wmin * (gcnt + 2) + gmin)
print(cost)

Solution (Python):
def solve(w_list, sort_list):
    ans = 0
    min_num = sort_list[0]
    for i in range(len(w_list)):
        x = sort_list.index(w_list[i])
        if x == i:
            continue
        sum_cost = 0
        min_loop_n = 10**4 + 1
        j = i
        loop_count = 0
        while True:
            loop_count += 1 
            sum_cost += w_list[j]
            min_loop_n = min(min_loop_n, w_list[j])
            if x == i:
                break
            w_list[x], w_list[j] = w_list[j], w_list[x]
            x = sort_list.index(w_list[j])
        ans += min(sum_cost + (loop_count-2)*min_loop_n, sum_cost + min_loop_n + (loop_count+1)*min_num)
    return ans
        
            
            
n = int(input())
w_list = list(map(int, input().split()))
sort_list = sorted(w_list)
print(solve(w_list, sort_list))

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

visited = [0] * n  
idxs = {}  
for i, b in enumerate(B):
    idxs[b] = i

saisyo = min(A)  

ans = 0
for i in range(n):
    if visited[i]:
        continue  
    cur = i  
    S = 0  
    n2 = 0
    m = float("inf")
    while True:
        visited[cur] = True
        S += A[cur]
        m = min(m, A[cur])
        n2 += 1
        cur = idxs[A[cur]]
        if visited[cur]:
            break 
    ans += min(m*(n2-2)+S, m+S+(1+n2)*saisyo)

print(ans)

Solution (Python):
import sys

n = int(input())
a = list(map(int, input().split()))
b= sorted(a)

ans = 0
for i in range(n):
    w = 0
    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
        w += b[x] + b[i]
        x = y
    if cnt > 0: 
        ans += min(w, (b[i] + b[0]) * 2 + w - (b[i] - b[0]) * cnt) 

print(ans)

Solution (Python):
import copy
INFTY=1000000000
MAX = 1000
VMAX = 100000

def solve(W,N,VMAX):
    T = [-1 for _ in range(VMAX)]
    for i in range(N):
        ans = 0
        V = [False for _ in range(N)]
        WW=copy.deepcopy(W)
        WW.sort()
        for i in range(N):
            T[WW[i]] = i
        for i in range(N):
            if V[i]:
                continue
            cur = i
            S = 0
            m = VMAX
            an = 0
            while True:
                V[cur] = True
                an += 1
                v = W[cur]
                m = min(m,v)
                S += v
                cur = T[v]
                if V[cur]:
                   break
            ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans

N = int(input())
W = list(map(int,input().split()))
s = min(W)
ans = solve(W,N,VMAX)
print(ans)

Solution (Python):
mp = {}
MAXN = 1010
mini =  100000
w = [0] * MAXN
done = [False] * MAXN

n = int(input())
w1 = [int(i) for i in input().split()]

for index, value in enumerate(w1):
    w[index] = value

for i in range(n):
    mp[w[i]] = 0
    mini = min(mini, w[i])

k = 0
for i in sorted(w1):
    mp[i] = k
    k += 1

ans = 0
for i in range(n):
    if done[i]: continue
    cnt = 0
    now = i
    mi = 100000
    total = 0
    while (True):
        if done[now]: break
        cnt += 1
        done[now] = True
        mi = min(mi, w[now])
        total += w[now]
        now = mp[w[now]]
    tmp = total + (cnt - 2) * mi
    tmp = min(tmp, total + mi + mini * (cnt + 1))
    ans += tmp
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):
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):
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):

def resolve():
    def solve(n, arr):

        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
        minV = 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, S+(an+1)*minV+m)
        return ans

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

if __name__ == '__main__':
    resolve()

Solution (Python):
def solve(A,n,s):
    ans = 0

    V = [False for i in range(n)] 
    B = sorted(A)
    T = [None for i in range(10001)]
    for i in range(n):
        T[B[i]] = i
    for i in range(n):
        if V[i]: 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
        ans += min(S+(an-2)*m, m+S+(an+1)*s)
    return ans

n = int(input())
A = [int(x) for x in input().split()]
s = min(A)

ans = solve(A,n,s)
print(ans)

Solution (Python):
n = int(input())
w = list(map(int,input().split()))
A = dict(zip(sorted(w), w))
min_value = min(A)
A = {k:v for k,v in A.items() if k != v or k == min_value}
totalcost = 0

while len(A) > 1:
    i_move_count = 0
    i = min_value
    if min_value == A[min_value]:
        i = min([v for v in A if v != min_value])

    while A[i] != i:
        j = A[i]
        A[i] = A[j]
        A.pop(j)
        i_move_count += 1
        totalcost += j

    if i != min_value:
        A.pop(i)

    totalcost += min((i * i_move_count), ((min_value * i_move_count) + (min_value + i) * 2))

print(totalcost)

Solution (Python):
n = int(input())
w = list(map(int, input().split()))
s = sorted(w)

cost = 0
for i in range(n):
    
    now_v = s[i]
    now_idx = w.index(s[i])
    j = 0 
    while now_idx > i:
        j += 1
        target_v = s[now_idx]
        target_idx = w.index(target_v)
        cost += w[target_idx] 
        w[now_idx], w[target_idx] = w[target_idx], w[now_idx]
        now_idx = target_idx
    
    
    
    
    
    
    
    cost += min(now_v * j, now_v * 2 + s[0] * (j + 2))
print(cost)

Solution (Python):
n = int(input())
a = [int(_) for _ in input().split()]

done = {}
for i in range(n):
    done[a[i]] = 0


direct = {}
a_sorted = sorted(a)
for i in range(n):
    direct[a_sorted[i]] = i


group_list = []
for i in range(n):
    if done[a[i]] == 1:
        continue
    else:
        f = a[i]
        done[f] = 1
        group = [f]
        n = f
        while a[direct[n]] != f:
            n = a[direct[n]]
            done[n] = 1
            group.append(n)
        group_list.append(group)


m = a_sorted[0]
cost = 0
while len(group_list) > 0:
    group = group_list.pop()
    if len(group) == 1:
        continue
    else:
        cost += min(sum(group) + (len(group) - 2) * min(group), sum(group) + min(group) + (len(group) + 1) * m)
print(cost)

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

def cycle_search(i):
    next_search_ind=i
    ret=[]
    while 1:
        now_ind=next_search_ind
        next_search_ind=sorted_A.index(A[now_ind])
        ret.append(A[now_ind])
        cycle_searched[now_ind]=True
        if cycle_searched[next_search_ind]:
            break
    return ret


sorted_A=sorted(A)

cycles=[]
cycle_searched=[False]*n

for i in range(n):
    if cycle_searched[i] == False:
        cycles.append(cycle_search(i))

ans=0
min_A=sorted_A[0]
for cycle in cycles:
    cycle_len=len(cycle)
    if cycle_len == 1:
        continue
    else:
        ans1 = sum(cycle)+(cycle_len-2)*min(cycle)
        min_cycle=min(cycle)
        ans2 = sum(cycle)-min_cycle+min_A+(cycle_len-2)*min_A+2*(min_A+min_cycle)
        ans += min(ans1,ans2)

print(ans)

Solution (Python):
n = int(input())
arr = list(map(int, input().split()))
idx = {}
for i, a in enumerate(sorted(arr)):
    idx[a] = i
visit = [False]*n
Min = min(arr)
ans = 0
for i in range(n):
    if visit[i]:
        continue
    visit[i] = True
    now = idx[arr[i]]
    tmp_min = arr[i]
    tot = tmp_min
    cnt = 1
    while now != i:
        visit[now] = True
        tot += arr[now]
        cnt += 1
        if tmp_min > arr[now]:
            tmp_min = arr[now]
        now = idx[arr[now]]
    ans += min(tot + (cnt - 2)*tmp_min, tot + tmp_min + (cnt + 1)*Min)
print(ans)

Solution (Python):
WMAX = 10 ** 4 + 1
N = int(input())
W1 = [int(w) for w in input().split()]
W2 = sorted(W1)
W3 = {}
mn1 = min(W1)
V = [False] * N

for i, w in enumerate(W2):  W3[w] = i

cost = 0
for i in range(N):
    if V[i]: continue
    cur = i
    S = 0
    N2 = 0
    mn2 = WMAX
    while True:
        V[cur] = True
        S += W1[cur]
        mn2 = min(mn2, W1[cur])
        N2 += 1
        cur = W3[W1[cur]]
        if V[cur]: break
    cost += min(mn2 * (N2 - 2) + S, mn2 + S + (1 + N2) * mn1)

print(cost)

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

_W = W[:]
_W.sort()
m = _W[0]

C = [None for _ in range(_W[n - 1] + 1)]
V = [False for _ in range(_W[n - 1] + 1)]

for i in range(n):
    C[_W[i]] = W[i]

r = 0

for i in _W:
    if V[i]:
        continue
    nxt = C[i]
    V[i] = True
    if nxt == i or V[nxt]:
        continue
    sum_w = i
    min_w = i
    c = 1
    while V[nxt] is False:
        V[nxt] = True
        sum_w += nxt
        nxt = C[nxt]
        c += 1
    r += min(sum_w + (c - 2) * min_w, sum_w + min_w + (c + 1) * m)

print(r)

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-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())
A = list(map(int, input().split()))
origin = list(range(N))

B = sorted(zip(A, origin), key=lambda x: x[0])


class UnionFind():
    def __init__(self, n):
        self.g = [[i] for i in range(n)]

    def root(self, x):
        if self.is_root(x):
            return x

        self.g[x] = self.root(self.g[x])
        return self.g[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        
        if x < y:
            x, y = y, x
        self.g[y] += self.g[x]
        self.g[x] = y

        return True

    def size(self, x):
        return -self.root(x)

    def is_root(self, x):
        if type(self.g[x]) is list:
            return True
        return False


G = UnionFind(N)
for i, b in enumerate(B):
    G.unite(i, b[1])


min_g = min(A)
cost = 0
for i in range(N):
    if G.is_root(i):
        W = [A[j] for j in G.g[i]]
        n_w = len(W)
        sum_w = sum(W)
        min_w = min(W)

        cost1 = sum_w + min_w*(n_w-2)
        cost2 = cost1 + 2*(min_w + min_g) - (min_w-min_g)*(n_w-1)
        cost += min(cost1, cost2)

print(cost)

Solution (Python):

def solve(n,num_list,s):
    ans = 0
    
    V = [False for _ in range(n)]
    
    
    sorted_num_list = sorted(num_list)

    
    T = [None for _ in range(10000+1)]
    for i in range(n):
        T[sorted_num_list[i]] = i

    
    for i in range(n):

        
        if V[i]:
            continue

        cur = i
        
        
        S = 0

        
        m = 10000

        
        an = 0

        
        while True:
            V[cur] = True
            an += 1
            v = num_list[cur]
            m = min(m,v)
            S += v
            cur = T[v]
            if V[cur]:
                break
        ans += min(S + (an - 2)*m,m+S+(an+1)*s)
    return ans




if __name__ == "__main__":
    n = int(input())
    num_list = list(map(int,input().split()))
    s = min(num_list)
    ans = solve(n,num_list,s)
    print(ans)