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):
def calcurate_cost(A, B, n):
    cost = 0
    s = min(A)
    V = [False] * n
    T = { j:i for i, j in enumerate(B) }
    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = 0
        an = 0
        m = 10000
        while True:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
            if V[cur]:
                break
        cost += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return cost
    
def minimum_cost_sort(A, n):
    B = sorted(A)
    return calcurate_cost(A, B, n)

n = int(input())
A = [int(i) for i in input().split()]
print(minimum_cost_sort(A, n))

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)

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)

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)

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

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):
N = int(raw_input())
W = map(int, raw_input().split())
T = sorted(W)
move = {}
for x in W:
    index = T.index(x)
    if x != W[index]:
        move[x] = W[index]

cycle = []
while len(move) > 0:
    l = []
    k, v = move.popitem()
    l.append(k)
    nk = v
    while nk != k:
        nv = move[nk]
        del move[nk]
        l.append(nk)
        nk = nv
    cycle.append(l)
cost = 0
for l in cycle:
    n = len(l)
    minCost = sum(l) + (n-2) * min(l)
    otherCost = sum(l) + min(l) + (n+1) * min(W)
    cost += minCost if minCost < otherCost else otherCost
print cost

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):
def perfect_swap():
    global n, a, b, cost
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            ai, aj = a[i], a[j]
            if ai == b[j] and aj == b[i]:
                a[i], a[j] = aj, ai
                cost += ai + aj


def lowest_swap():
    global n, a, b, cost
    for i in range(n - 1):
        bi, tmp_cost, count = b[i], 0, 0
        while a[i] != bi:
            si = a.index(bi)
            bsi = b[si]
            sj = a.index(bsi)
            a[si], a[sj] = bsi, bi
            tmp_cost += bi + bsi
            count += 1
        if count:
            if i:
                b0 = b[0]
                cost += min(tmp_cost, (bi + b0) * 2 + tmp_cost - (bi - b0) * count)
            else:
                cost += tmp_cost


n, a, cost = int(input()), list(map(int, input().split())), 0
b = sorted(a)
perfect_swap()
lowest_swap()
print(cost)

Solution (Python):
n, a, cost = int(input()), list(map(int, input().split())), 0
b = sorted(a)
b0 = b[0]
for i in range(n - 1):
    bi, tmp_cost, count = b[i], 0, 0
    si = a.index(bi)
    while si != i:
        bsi = b[si]
        sj = a.index(bsi)
        a[si], a[sj] = bsi, bi
        tmp_cost += bi + bsi
        count += 1
        si = sj
    if count:
        cost += min(tmp_cost, (bi + b0) * 2 + tmp_cost - (bi - b0) * count)
print(cost)

Solution (Python):
def get_weights():
    raw_input()
    return map(int, raw_input().split())


def minimam_cost_sort(weights):
    mw = min(weights)
    s_w = sorted(weights)
    lol = []
    for i in range(len(weights)):
        if weights[i] != 0:
            j = weights[i]
            idx = s_w.index(j)
            weights[i] = 0
            l = [j]
            while weights[idx] != 0:
                l.append(weights[idx])
                j = weights[idx]
                weights[idx] = 0
                idx = s_w.index(j)
            l.sort()
            lol.append(l)

    lol.sort()
    s = 0
    for l in lol:
        s += get_wol(l, mw)

    print s

def get_wol(l, mw):
    sub = (l[0] - mw) * (len(l) - 1) - (l[0] + mw) * 2
    s = sum(l) + (l[0] * (len(l) - 2))
    if sub > 0:
        return s - sub
    return s

minimam_cost_sort(get_weights())

Solution (Python):

import copy

class BagsWithWeight(list):
    def __init__(self, l):
        super(BagsWithWeight, self).__init__(l)
        self.sorted_weights = list(sorted(self))

    def get_lists_of_loop(self):
        """???????????????????????????????????????????±??????????
        ????????\??????????????????????????????????????¬??\???????????? index ???????????????????????????
        ??????????????????????????¬??\???????????? index ????????£???????????¨?????????????????????????????????
        ?????????????????§?????????????????????????????¨ 1 ????????????????????????
        ????????????????????????????????? 1 ????????\???????????§??????????????????????????????????????????
        out: ListOfLoops     ??¨?????? loop ????????????
        """
        c_weights = copy.copy(self)
        loops = Loops()
        for i in range(len(self)):
            loop = []
            index = i
            while c_weights[index] != -1:
                loop.append(c_weights[index])
                c_weights[index] = -1
                index = self.get_index_of_sorted_bag(index)
            if loop:
                loops.append(loop)
        return loops

    def get_index_of_sorted_bag(self, index):
        """???????????????????????????????????????????????? index ????????????
        in:  index    int    ??????????????? index ????±?????????????????????? index
        out: int    ?????????????????????????????? index
        """
        return self.sorted_weights.index(self[index])


class Loops(list):
    def append(self, elm):
        elm.sort()
        elm = Loop(elm, self)
        super(Loops, self).append(elm)

    def get_minimum_element(self):
        return min(min(self))

    def get_cost(self):
        return sum(map((lambda loop: loop.get_cost_of_sorting()), self))


class Loop(list):
    def __init__(self, loop, loops):
        super(Loop, self).__init__(loop)
        self.loops = loops
    
    def get_minimum_weight_of_outer(self):
        return self.loops.get_minimum_element()

    def get_cost_of_sorting(self):
        """Loop ?????¨???????°??????????????±??????????
        """
        cost = sum(self) + min(self) * (len(self) - 2)
        cost_reduced = self.get_how_much_outer_minimum_weight_bag_reduces_cost()
        if cost_reduced > 0:
            return cost - cost_reduced
        else:
            return cost


    def get_how_much_outer_minimum_weight_bag_reduces_cost(self):
        """Loops ???????°????????????????????????£???????????§???????????????????±??????????
        List of Loops ??????????°?????????????????´????
        Loop ??????????°?????????????????´???¨??\????????????
        ?????????????????£?????????????????§???????????????????????????
        ??????????????? len(loop) - 1 ??????????????????????????????????°???????????????????????????????
        out: int    ????????§???????????????
        """
        return ((min(self) - self.get_minimum_weight_of_outer()) *
                    (len(self) - 1) -
                    (min(self) + self.get_minimum_weight_of_outer()) * 2)


def get_weights():
    raw_input()
    return map(int, raw_input().split())

bww = BagsWithWeight(get_weights())
loops = bww.get_lists_of_loop()
print loops.get_cost()

Solution (Python):
"""Minimum cost Sort."""

def make_cycle(A):
    """Return a list which has the minimum element of A and
    switch elements cycles as list.

    A is a list whose elements' type is 'int'.

    Each cycle list has its minimum elements in the first index.
    """
    B = list(A)
    B.sort()
    cycle_list = [B[0]]
    for i, b in enumerate(B):
        if b != None:
            new_cycle = []
            new_cycle.append(b)
            B[i] = None
            si = A.index(b)
            while si != i:
                st = B[si]
                new_cycle.append(st)
                B[si] = None
                si = A.index(st)
            cycle_list.append(new_cycle)
    return cycle_list

def min_sorting_cost(A):
    """Return the minimum cost of sorting A.

    A is a list whose elements' type is 'int'.
    """
    cycles = make_cycle(A)
    min_w = cycles[0]
    cost = 0
    for c in cycles[1:]:
        n = len(c)
        min_cw = c[0]
        dec = (n - 1) * (min_cw - min_w)
        inc = 2 * (min_w + min_cw)
        if dec < inc:
            cost += sum(c) + min_cw * (n - 2)
        else:
            cost += sum(c) + min_cw * (n - 2) - dec + inc
    return cost


n = int(input())

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

ans = min_sorting_cost(A)

print(ans)

Solution (Python):
"""Minimum cost Sort."""

def min_cost_sort(A):
    """Sort list A in ascending order.
 
    And return the switching cost in sorting.
    """
    B = list(A)
    B.sort()
    cost = 0
    min_w = B[0]
    for i, b in enumerate(B):
        tmp_cost = 0
        bi = A.index(b)
        n = 1
        while bi != i:
            n += 1
            st = B[bi]
            si = A.index(st)
            tmp_cost += b + st
            A[bi], A[si] = st, b
            bi = si
        dec = (n - 1) * (b - min_w)
        inc = 2 * (min_w + b)
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost


n = input()

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

ans = min_cost_sort(A)

print(ans)

Solution (Python):
"""Minimum cost Sort."""

def min_cost_sort(A):
    """Sort list A in ascending order.
 
    And return the switching cost in sorting.
    """
    B = list(A)
    B.sort()
    cost = 0
    min_w = B[0]
    for i, b in enumerate(B):
        tmp_cost = 0
        bi = A.index(b)
        n = 1
        while bi != i:
            n += 1
            st = B[bi]
            si = A.index(st)
            tmp_cost += b + st
            A[bi], A[si] = st, b
            bi = si
        dec = (n - 1) * (b - min_w)
        inc = 2 * (min_w + b)
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost


n = input()

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

ans = min_cost_sort(A)

print(ans)

Solution (Python):
"""Minimum cost Sort."""

def min_cost_sort(A):
    """Sort list A in ascending order.
 
    And return the switching cost in sorting.
    """
    B = list(A)
    B.sort()
    cost = 0
    min_w = B[0]
    for i, b in enumerate(B):
        tmp_cost = 0
        bi = A.index(b)
        cnt = 0
        while bi != i:
            cnt += 1
            st = B[bi]
            si = A.index(st)
            tmp_cost += b + st
            A[bi], A[si] = st, b
            bi = si
        if cnt:
            dec = cnt * (b - min_w)
            inc = 2 * (min_w + b)
            if dec < inc:
                cost += tmp_cost
            else:
                cost += tmp_cost - dec + inc
    return cost


n = input()

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

ans = min_cost_sort(A)

print(ans)

Solution (Python):
"""Minimum cost Sort."""

def min_cost_sort(A):
    """Sort list A in ascending order.
 
    And return the switching cost in sorting.
    """
    B = list(A)
    B.sort()
    cost = 0
    min_w = B[0]
    for i, b in enumerate(B):
        tmp_cost = 0
        bi = A.index(b)
        cnt = 0
        while bi != i:
            cnt += 1
            st = B[bi]
            si = A.index(st)
            tmp_cost += b + st
            A[bi], A[si] = st, b
            bi = si
        dec = cnt * (b - min_w)
        inc = 2 * (min_w + b)
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost


n = input()

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

ans = min_cost_sort(A)

print(ans)

Solution (Python):
n = int(raw_input())
W = map(int, raw_input().split())
s = min(W)
T = [0] * (max(W)+1)

def solve():
    ans = 0
    B = W[:]
    V = [False] * n

    B.sort()
    for i in xrange(n):
        T[B[i]] = i
    for i in xrange(n):
        if V[i]:
            continue
        cur = i
        S = 0
        m = max(W)+1
        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

def main():
    ans = solve()
    print ans
    return 0

main()

Solution (Python):
n = int(raw_input())
W = map(int, raw_input().split())
s = min(W)
T = [0] * (max(W)+1)

def solve():
    ans = 0
    B = W[:]
    V = [False] * n

    B = sorted(B)
    for i in xrange(n):
        T[B[i]] = i
    for i in xrange(n):
        if V[i]:
            continue
        cur = i
        S = 0
        m = max(W)+1
        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

def main():
    ans = solve()
    print ans
    return 0

main()

Solution (Python):
n, cost = int(input()), 0
num = list(map(int, input().split()))
num_s = sorted(num)
n0 = num_s[0]

for i in range(n - 1):
    ni, tmp, cnt = num_s[i], 0, 0
    si = num.index(ni)
    while si != i:
        nsi = num_s[si]
        sj = num.index(nsi)
        num[si], num[sj] = nsi, ni
        tmp += ni + nsi
        cnt += 1
        si = sj
    if cnt:
        cost += min(tmp, (ni + n0) * 2 + tmp - (ni - n0) * cnt)
print(cost)

Solution (Python):
import sys

def minimumCostSort(A):
    B = sorted(A)
    V = [False] * len(A)
    T = [0] * 10001
    ans = 0
    s = min(A)

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

    for i in range(len(A)):
        if V[i]:
            continue
        S = an = 0
        j = i
        m = 10000
        while True:
            V[j] = True
            an += 1
            v = A[j]
            m = min(m, v)
            S += v
            j = T[v]
            if V[j]:
                break
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    print minimumCostSort(A)

Solution (Python):
import sys

def minimumCostSort(A):
    B = sorted(A)
    V = [False] * len(A)
    T = [0] * 10001
    ans = 0
    s = min(A)

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

    for i in range(len(A)):
        if V[i]:
            continue
        S = an = 0
        j = i
        m = 10000
        while True:
            V[j] = True
            an += 1
            v = A[j]
            m = min(m, v)
            S += v
            j = T[v]
            if V[j]:
                break
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    print minimumCostSort(A)

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

    B = A[:]
    V = [False for i in A]
    B = sorted(B)
    T = [0 for i in range(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

MAX = 1000
VMAX = 10000


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

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

Solution (Python):

def MCS(A,n):
    B=sorted(A)
    B0=B[0]
    cost=0
    for i in range(n-1):
        Bi,t_cost,count=B[i],0,0
        si=A.index(Bi)
        while si!=i:
            bsi=B[si]
            sj=A.index(bsi)
            A[si],A[sj]=bsi,Bi
            t_cost+=Bi+bsi
            count+=1
            si=sj
        if count:
            cost+=min(t_cost,(Bi + B0) * 2 + t_cost - (Bi - B0) * count) 
    print(cost)
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    MCS(A,n)

Solution (Python):



def processA(target_list, correct_list, i):

    cost = 0
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
        
    return cost
    
def processB(target_list, correct_list, i):
    minv = correct_list[0]
    target = correct_list[i]

    if minv == target:
        return 10 ** 9
    cost = (minv + target)
    
    mmi = target_list.index(minv)
    smi = target_list.index(target)
    target_list[mmi], target_list[smi] = target_list[smi], target_list[mmi]
    
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(minv)
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
        
    return cost
    
def minimum_cost_sort(target_list):
    correct_list = sorted([a for a in target_list])
    cost = 0
    i = 0
    while not correct_list == target_list:
        cost_b = processB([a for a in target_list], correct_list, i)
        cost_a = processA(target_list, correct_list, i)
        cost += min(cost_a, cost_b)
        
        
        i += 1
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Solution (Python):
import functools

def find_all_rings(items):
    "items: (??°???, ?????????????????????????????????)"
    l = len(items)
    check_list = [False] * l
    rings = []
    i = 0
    while i < l:
        if check_list[i] == False:
            ring = []
            first = items[i]
            ring.append(first)
            check_list[i] = True
            item_index = first[1]
            item = items[item_index]
            while item[0] != first[0]:
                ring.append(item)
                check_list[item_index] = True
                item_index = item[1]
                item = items[item_index]
            rings.append(ring)
        i += 1
    return rings

def compute_ring_cost(min_all, ring):
    l = len(ring)
    if l <= 1:
        return 0
    w = [item[0] for item in ring]
    min_ring = min(w)
    sum_ring = sum(w)
    if (l + 1) * min_all < (l - 3) * min_ring:
        return sum_ring + min_ring + (l + 1) * min_all
    else:
        return sum_ring + (l - 2) * min_ring

n = int(input())
ns = list(map(int, input().split()))
items = []
sorted_items = []
for i in range(n):
    item = (ns[i], i)
    items.append(item)
    sorted_items.append(item)

sorted_items.sort(key = lambda x : x[0])

for i in range(n):
    item = sorted_items[i]
    items_index = item[1]
    items[items_index] = (item[0], i)

rings = find_all_rings(items)
compute_ring_cost1 = functools.partial(compute_ring_cost, min(ns))
print(sum(map(compute_ring_cost1, rings)))

Solution (Python):



import sys

MAX_VALUE = int(1e4 + 1)


def min_cost_sort():
    ans = 0
    for i in range(array_length):
        if check_order[i]:
            continue
        current_index = i
        circle_sum, circle_min, circle_size = 0, MAX_VALUE, 0
        while True:
            check_order[current_index] = True
            circle_size += 1
            current_value = array[current_index]
            circle_min = min(circle_min, current_value)
            circle_sum += current_value
            current_index = kv_reverse[current_value]
            if check_order[current_index]:
                break
        ans += min(circle_sum + (circle_size - 2) * circle_min,
                   circle_sum + circle_min + (circle_size + 1) * min_value)
    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    

    check_order = [False] * array_length
    kv_reverse = [-1] * MAX_VALUE
    compare_ans = sorted(array)
    min_value = compare_ans[0]
    for j in range(array_length):
        kv_reverse[compare_ans[j]] = j
    print(min_cost_sort())

Solution (Python):



import sys

MAX_VALUE = int(1e4 + 1)


def min_cost_sort():
    ans = 0
    for i in range(array_length):
        if check_order[i]:
            continue
        current_index = i
        circle_sum, circle_min, circle_size = 0, MAX_VALUE, 0
        while True:
            check_order[current_index] = True
            circle_size += 1
            current_value = array[current_index]
            circle_min = min(circle_min, current_value)
            circle_sum += current_value
            current_index = value_to_index[current_value]
            if check_order[current_index]:
                break
        ans += min(circle_sum + (circle_size - 2) * circle_min,
                   circle_sum + circle_min + (circle_size + 1) * min_value)
    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    

    check_order = [False] * array_length
    value_to_index = dict()
    compare_ans = sorted(array)
    min_value = compare_ans[0]
    for j in range(array_length):
        value_to_index[compare_ans[j]] = j
    print(min_cost_sort())

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()))
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
    c+=min(t,(b[i]+b[0])*2+t-(b[i]-b[0])*cnt)
print(c)

Solution (Python):


MAX_NUM = int(1E4 + 1)

if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().strip().split()]
    sorted_A = sorted(A)
    smallest = sorted_A[0]
    correct_pos = [0] * MAX_NUM
    flag_A = [False] * MAX_NUM
    for i, val in enumerate(sorted_A):
        correct_pos[val] = i

    ans = 0
    for i in range(len(A)):
        if flag_A[A[i]]:
            continue
        next_pos = i
        sum = 0
        m = 1E4
        an = 0
        while True:
            an += 1
            val = A[next_pos]
            sum += val
            m = min([m, val])
            flag_A[A[next_pos]] = True
            next_pos = correct_pos[val]
            if flag_A[A[next_pos]]:
                break
        ans += min([sum + (an - 2) * m, m + sum + (an + 1) * smallest])

    print(ans)

Solution (Python):
def minimum_cost_sort(A):
  cost = 0
  B = sorted(A)
  for i in range(len(B)):
    x = A.index(B[i])
    cnt = 0
    tmp = 0
    while x != i:
      y = A.index(B[x])
      A[x], A[y] = A[y], A[x]
      tmp += A[x] + A[y]
      cnt += 1
      x = y
    if cnt > 0:
      
      
      
      
      cost += min(tmp, (B[i] + B[0]) * 2 + tmp - (B[i] - B[0]) * cnt)
  return cost

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

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):
MAX = 1000
VMAX = 10000
n = int(input())
A = [int(i) for i in input().split()]
V = [False] * MAX
def solve():
    B = A[:]
    T = [0] * (VMAX + 1)
    B.sort()
    ans = 0
    s = min(VMAX, min(A))
    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)
    print(ans)
solve()

Solution (Python):
def mklist(B,D,V):
    min = 10000
    for key,val in enumerate(B):
        D[val] = key
        V[val] = 0
        if min > val:
            min = val
    return min

def solve(A,V,D,min):
    cost = 0
    for key, val in enumerate(A):
        if V[val] != 0:
            continue
        W = []
        wmin = 10000
        tw = 0
        k1 = key
        v = val
        while(1):
            k2 = D[v]
            if V[v] == 1:
                break
            W.append(v)
            V[v] = 1
            if wmin > v:
                wmin = v
            tw += v
            
            k1 = k2
            v = A[k1]
        n = len(W)
        t1 = tw + ((n - 2) * wmin)
        t2 = tw + wmin + ((n + 1) * min)
        if t1 < t2:
            cost += t1
        else:
            cost += t2
    return cost

def main():
    num = int(input())
    A = list(map(int,input().split()))
    B = sorted(A)
    D = {}
    V = {}
    min = mklist(B,D,V)
    cost = solve(A,V,D,min)
    print(cost)

if __name__ == '__main__':
    main()

Solution (Python):
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def mincost(A):
    B = sorted(A)
    cost = 0
    
    for i, bi in enumerate(B):
        t = 0
        j = A.index(bi)
        tmp_cost = 0
        
        
        while j != i:
            t += 1
            bj = B[j]
            k = A.index(bj)
            tmp_cost += bi + bj
            swap(A,j,k)
            j = k
        
        
        dec = t * (bi - B[0])
        inc = 2 * (bi + B[0])
        
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    cost = mincost(A)
    print(cost)

Solution (Python):
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def mincost(A):
    B = sorted(A)
    cost = 0
    b0 = B[0]
    
    for i, bi in enumerate(B):
        t = 0
        j = A.index(bi)
        tmp_cost = 0
        
        
        while j != i:
            t += 1
            bj = B[j]
            k = A.index(bj)
            tmp_cost += bi + bj
            swap(A,j,k)
            j = k
        
        
        dec = t * (bi - b0)
        inc = 2 * (bi + b0)
        
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    cost = mincost(A)
    print(cost)

Solution (Python):
n = int(input())
line = input()
L = [int(x) for x in line.split()]

flags = [False] * n
loops = []

S = sorted(L)
I = [S.index(x) for x in L]
for idx, x in enumerate(I):
    if flags[x]:
        continue
    if x == idx:
        flags[idx] = True
        continue

    ws = []
    while S[x] not in ws:
        flags[x] = True
        ws.append(S[x])
        x = I[x]
    loops.append(ws)

cost = 0
for loop in loops:
    a = sum(loop) + (len(loop) - 2) * min(loop)
    b = sum(loop) + min(loop) + (len(loop) + 1) * min(L)
    cost += min(a, b)

print(cost)

Solution (Python):
n = int(input())
line = input()
L = [int(x) for x in line.split()]

flags = [False] * n
loops = []

S = sorted(L)
for idx, x in enumerate(L):
    k = S.index(x)
    if flags[k]:
        continue
    if k == idx:
        flags[k] = True
        continue

    ws = []
    while x not in ws:
        flags[k] = True
        ws.append(x)
        x = L[k]
        k = S.index(x)
    loops.append(ws)

cost = 0
for ws in loops:
    n = len(ws)
    a = sum(ws) + (n - 2) * min(ws)
    b = sum(ws) + min(ws) + (n + 1) * min(L)
    cost += min(a, b)

print(cost)

Solution (Python):



if __name__ == '__main__':

    n = int(input())
    A = [int(a) for a in input().split(" ")]
    B = A.copy()
    B.sort()
    V = [False]*n
    T = {B[i]:i for i in range(n)}

    ans = 0
    s = min(A)

    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = 0 
        m = 10000 
        an = 0 
        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)

    print(ans)